Váš první dotaz by byl správný, pokud byste použili AND spíše než OR .
Možná vám to přijde jednodušší jako:
where not (city like 'A%' or city like 'E%' or . . . ) and
. . .
Podle logických pravidel je to ekvivalentní:
where city not like 'A%' and city not like 'E%' and . . . ) and
. . .
Pokud jde o regulární výraz, má pouze srovnání na začátku řetězce:
where not regexp_like(lower(city), '^[aeiou].*[aeiou]$')