Você não está ancorando a expressão. Pode combinar no meio, então quaisquer vogais "fora" do seu jogo são permitidas.
Adicione um ^ e $ para evitar isso.
$ echo abstemiousnesses | grep -iE '[^aeiou]*a[^aeiou]*e[^aeiou]*i[^aeiou]*o[^aeiou]*u[^aeiou]*'
abstemiousnesses
$ echo abstemiousnesses | grep -iE '^[^aeiou]*a[^aeiou]*e[^aeiou]*i[^aeiou]*o[^aeiou]*u[^aeiou]*$'