Tendrías que utilizar una consulta como esta:
Código PHP:
<?
$consulta1 = "SELECT id FROM registros_cat WHERE ....."; //Esta es la consulta para saber cuales son las categorias en las que el cliente esta registrado
$consulta2 = "SELECT categoria FROM registros_cat WHERE categoria NOT IN ($consulta1)"; //Fijate que utilize $consulta1 para armar $consulta2, no es necesario ejecutarla antes
$resultado = mysql_query($consulta2); //Esto debería devolverte las categorias en las que no esta registrado el usuario.
?>
Espero que te sirva.
Saludos.