3 strokes sh?aved.

#!perl -aln
$$_=y/aAeEiIoOuU//for@F;print"$$_ $_"for sort{$$b-$$a||$a cmp$b}@F
[download]

Using a G-R transform (and assuming less than 9 vowels per word) saves 8 more.

#!perl -an
print+map{/./;9-$&.$'}sort map{9- y/aAeEiIoOuU//." $_\n"}@F
[download]

/-\

Oh, man I'm rusty. Here are a few minor tweaks. For the full version, one less:

$$_=lc=~y/aeiou//for@F;print"$$_ $_"for sort{$$b-$$a||$a cmp$b}@F
[download]

For the "less than ten vowels" version, you can also lose one by getting rid of that space after the "map{9-".

Finally, if they meant increasing order of vowel count and less than nine vowels, then we can do much better ;)

-an print sort map y/aAeEiIoOuU//." $_\n",@F
[download]

For the "less than ten vowels" version, you can also lose one by getting rid of that space after the "map{9-".

Alas, Perl complains with Unrecognized file test: -y if you try that. However, using your lc trick saves two more strokes:

print+map{/./;9-$&.$'}sort map{9-lc=~y/aeiou//." $_\n"}@F
[download]

You could allow up to 90 vowels (at the cost of 3 strokes) by changing 9 to 99 and . to ..