On Linux, without the -Mlocale switch, I get the same behaviour that you get on Windows. To get the result you wish, I used Unicode::Collate e.g.

#! perl

use strict;
use warnings;
use utf8;
use Unicode::Collate;

binmode STDOUT => ':utf8';

my @words = ( "Maria Lenore", "Mária Helena", "María Dolores" );
my $col = Unicode::Collate->new(level => 1);

my @sorted = $col->sort(@words);

if ( "@sorted" eq "María Dolores Mária Helena Maria Lenore" ) {
    print("Sorted OK\n");
}
elsif ( "@sorted" eq "Maria Lenore María Dolores Mária Helena" ) {
    print("Sorted C (ASCII)\n");
}
else {
    print("Sort failed: @sorted\n");
}
[download]

I had these bookmarked ages ago, but didn't look at them until today:

• Case- and Accent-insensitive Sorting
• What's Wrong with sort and How to Fix It