It'll fail if one of the numbers exceed 4294967295 (2^32, the maximum number that will fit in an unsigned long).

Mine, like yours, is tailored to the OPs data. However, yours has a flaw that will manifest itself even within the confines of the OPs data format.

It doesn't preserve pre-exist leading zeros:

print for map{
    s/\D\K0+//; $_
} sort map{
    sprintf "%s%02d", /(\D+)(\d+)/
} qw[ St0 St01 St00009 ];;
St
St1
St9
[download]

For a generic solution, you can take the pack solution to the next level, deal with 2^32 issue and allow for multiple numeric fields:

my @g = qw[
    St1x7 St1x23 St10x355 Stb10x100 Sta2x9 St2x1 Stbbb12x5 Staaa12x4 S
+t6x33333 
    St6x0 St8 St0x11111111111111 St0x22222222222222 AAAAAAAAAAAAAAAAAA
+ ZZZZZZZZZZZ
];;

print for map{ 
    my $n = unpack 'N', substr $_, -4;  
    substr $_, $n, length() - $n - 4  
} sort map{ 
    (my $x = $_) =~ s[(\d{,9})][ pack 'N', $1]ge; 
    pack 'A*A*N', $x, $_, length( $x ) 
} @g;;

AAAAAAAAAAAAAAAAAA
St0x11111111111111
St0x22222222222222
St10x355
St1x23
St1x7
St2x1
St6x0
St6x33333
St8
Sta2x9
Staaa12x4
Stb10x100
Stbbb12x5
ZZZZZZZZZZZ
[download]

But the extra code involved will slow things down, so you only use it if you need to, or when you do not know in advanced the format of the data.