Su primera consulta sería correcta si usara AND en lugar de OR .
Puede encontrar la lógica más simple como:
where not (city like 'A%' or city like 'E%' or . . . ) and
. . .
Según las reglas de la lógica, esto es equivalente a:
where city not like 'A%' and city not like 'E%' and . . . ) and
. . .
En cuanto a la expresión regular, solo tiene la comparación al principio de la cadena:
where not regexp_like(lower(city), '^[aeiou].*[aeiou]$')
