The recordset is the correct way to do it.
The recordset should be set to filter on the selection made and the users ID.
In the validation, use numeric validation.
for the server variable, use:
$totalRows_<recordsetName>
where <recordsetNamer> is the name of the recordset.
for the numeric validation, set the minimum to -1 and the max to 0. That will pass validation only if the Recordset does not return any rows.