Votre première requête serait correcte si vous utilisiez AND plutôt que OR .
Vous pourriez trouver la logique plus simple que :
where not (city like 'A%' or city like 'E%' or . . . ) and
. . .
Selon les règles de la logique, cela équivaut à :
where city not like 'A%' and city not like 'E%' and . . . ) and
. . .
Quant à l'expression régulière, elle n'a que la comparaison en début de chaîne :
where not regexp_like(lower(city), '^[aeiou].*[aeiou]$')
