I started this before the last two comments, it took me awhile using Data::Dumper to figure it out. Here is another using XML::Simple but I'll bet it's slower than Twig!

#!/usr/bin/perl

use warnings;
use strict;

use XML::Simple;

my $xmlstring = do { local $/; <DATA> };
my $xs = new XML::Simple;
my $xml = $xs->XMLin($xmlstring);

foreach(@{$xml->{address}}) {
    my @tmp = sort { $a->{refid} cmp $b->{refid} } @{$_->{ref}};
    $_->{ref} = \@tmp;
}

print $xs->XMLout($xml);

__DATA__
<opt>
xxxdata
<address>
<state>address1</state>
<ref refid="aaf1">1</ref>
<ref refid="AAF1">2</ref>
<ref refid="e2"/>
<ref refid="e4"/>
<ref refid="aff4">4</ref>
</address>
<ref refid="zzz9">2</ref>
<ref refid="aff1">1</ref>
<address>
<state>address1</state>
<ref refid="aff1">1</ref>
<ref refid="aff2">2</ref>
<ref refid="e4"/>
<ref refid="aff3">3</ref>
</address>
</opt>
[download]