What you want is:

my @tosort;
while( <DATA> ) {
  if( m|<address>| .. m|</address>| and not m|</?address>| ) {
    push @tosort, $_;
    next
  }
  print for sort splice @tosort;
  print
}
[download]

Ah, the awk  .. operator.... :-P