Sua primeira consulta estaria correta se você usasse
AND em vez de OR . Você pode achar a lógica mais simples como:
where not (city like 'A%' or city like 'E%' or . . . ) and
. . .
Pelas regras da lógica, isso é equivalente a:
where city not like 'A%' and city not like 'E%' and . . . ) and
. . .
Quanto à expressão regular, ela tem apenas a comparação no início da string:
where not regexp_like(lower(city), '^[aeiou].*[aeiou]$')
