Uw eerste vraag zou correct zijn als u AND . had gebruikt in plaats van OR .
Misschien vind je het de logica eenvoudiger als:
where not (city like 'A%' or city like 'E%' or . . . ) and
. . .
Volgens de regels van de logica is dit gelijk aan:
where city not like 'A%' and city not like 'E%' and . . . ) and
. . .
Wat betreft de reguliere expressie, deze heeft alleen de vergelijking aan het begin van de string:
where not regexp_like(lower(city), '^[aeiou].*[aeiou]$')