La tua prima richiesta sarebbe corretta se utilizzassi AND anziché OR .
Potresti trovare la logica più semplice come:
where not (city like 'A%' or city like 'E%' or . . . ) and
. . .
Per le regole della logica, questo equivale a:
where city not like 'A%' and city not like 'E%' and . . . ) and
. . .
Per quanto riguarda l'espressione regolare, ha solo il confronto all'inizio della stringa:
where not regexp_like(lower(city), '^[aeiou].*[aeiou]$')
