#!/usr/bin/perl -w
use strict;
use Data::Dumper;

chomp( my @array = <DATA> );

@array = map { $_->[0] }
         sort { $a->[1] <=> $b->[1] }
         map { [ $_, split /!/ ] } @array;

print Dumper \@array;

__DATA__
100!100!key!date!2..
100!100!key!store!
110!110!P\d\d\d_.*\.\d{6,}\.EMRemr
120!125!
1!yeada
130!132!
140!133!
150!134!
500!blah
160!135!arbor_ama
503!blah
170!136!
505!blah
180!137!
190!138!