Well it wasn't part of the original problem statement, so the solution allows sort to pick any order it chooses for elements with the same vowel string. You can tack on the original word to the end of the vowels string to sort by consonants when vowel strings match.

Here is that idea, but using GRT Sort instead of ST:

use 5.014;
say join ', ',
    map {s/.*\0//r}
    sort
    map {tr/aeiou//cdr."\0$_"}
    qw( xexix babebib xaxexi babebibb );
[download]

babebib, babebibb, xaxexi, xexix
[download]

Nice. Since I added the second edge case, the above still doesn't address the sorting of "babebib" and "baebbib". Even though the first one is alphabetically first, the second should be first based on the positioning of the second vowel. That is at least how I would read the problem.

You are right, however, the initial problem was loosely stated, so there is definitely room for interpretation.

Update: The second case may not apply here because the initial question provides sample output that doesn't include the positioning of the vowels in the words. If positioning mattered, the output would actually be the following instead:

apparate albacore albatross panacea fanfare false parmesan candelabra 
+beans vermeil
[download]

#!/usr/bin/perl

use warnings;
use strict;
use feature qw{ say };

my @words = qw( xaxexix babebib xaxexi babebibb baebbib );

sub prepare_sort {
    my ( $vowels, $positions ) = ( '', '' );

    while (/([aeiou])/g) {
        $vowels .= $1;
        $positions .= sprintf '%03d', pos;
    }

    return [ $_, $positions, $vowels ];
}

say for map $_->[0],
  sort { $a->[2] cmp $b->[2] } # vowels sort
  sort { $a->[1] cmp $b->[1] } # positional sort
  sort { $a->[0] cmp $b->[0] } # alphabetical sort
  map prepare_sort(), @words;
[download]

baebibb
babebib
babebibb
xaxexi
xaxexix
[download]

Now that I think of it, it can be greatly simplified:

sub prepare_sort {
    return [ $_, tr/aeiou/z/cr, tr/aeiou//dr ];
}
[download]

Thanks to Zucan for the tip!

So we dont need a sub now:

#!/usr/bin/perl

use warnings;
use strict;
use feature qw{ say };

my @words = qw( xaxexix babebib xaxexi babebibb baebbib );

say for map $_->[0],
  sort { $a->[2] cmp $b->[2] } # vowels sort
  sort { $a->[1] cmp $b->[1] } # positional sort
  sort { $a->[0] cmp $b->[0] } # alphabetical sort
  map  [ $_, tr/aeiou/z/cr, tr/aeiou//dr ],
    @words;
[download]

map [ $_, tr/aeiou/ /r, tr/aeiou//cdr ]

If you want to sort alphabetically the words with the vowels at the same position, you can make just a very simple change to just one line of the original ST code suggested by choroba:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my @words = qw( fanfare apparate panacea parmesan albatross
                albacore false vermeil candelabra beans );

say for map $_->[0],
        sort { $a->[1] cmp $b->[1] || $a->[0] cmp $b->[0]}
        map [ $_, join q(), /[aeiou]/g ],
        @words;
[download]

$a->[1] cmp $b->[1]
[download]

$a->[0] cmp $b->[0]
[download]

I do not think that the other edge case you mention is compatible with the initial question.

That is a very good point, I never stopped to think if the words were the same. Realizing now that could be a possibility I will fix that. Thank you for pointing that out. I am new to Perl so I am just taking programming contest-esque problems and am trying to work them out to learn.