Lo svantaggio dell'utilizzo di una regola è che le regole riscrivono semplicemente la query dopo che è stata analizzata, quindi se i dati vengono aggiunti tramite un trigger, non si attiveranno. È più sicuro aggiungere un vincolo CHECK che chiama una funzione con la tua logica. Se seguo correttamente la tua logica, dovrebbe essere qualcosa del tipo:
CREATE OR REPLACE FUNCTION check_user_client(fkc int)
RETURNS boolean AS
$$
DECLARE
i int;
BEGIN
SELECT count(*) INTO i FROM legal_entity WHERE fk_client = fkc;
IF (i > 0) THEN
RETURN true;
END IF;
SELECT count(*) INTO i FROM user_client WHERE fk_client = fkc;
IF (i = 0) THEN
RETURN true;
END IF;
RETURN false;
END
$$ LANGUAGE plpgsql;
ALTER TABLE user_client ADD CONSTRAINT unique_user CHECK (check_user_client(fk_client));