Not so much golfed as untidy... :-(

Update: chopped out a few more strokes. later: and a few more...

sub n{for(\@a,\@b){@$_=split/(?<=\d)(?=\D)|(?<=\D)(?=\d)/,lc
shift@_};for(0..$#a){$j=$a[$_];$k=$b[$_];return$j=~/\d/&$k=~/\d/?($j==
+$k?next:$j<=>$k):($j=~/\D/&$k=~/\D/?($j
eq$k?next:$j cmp$k):(defined$k?$j cmp$k:1))}}




@testarray = (qw/86 101 10 20 1 A amstelveen a10 A1
Amsterdam Amsterdam5 Amsterdam40 Amsterdamned
112kimn678mn09 112kimm678mn19 112kimm678mn09
112kimm678mn9 865314457646576532325988/);

print join "\n", sort { n($a,$b)} @testarray;
[download]