As others have mentioned, XML might not be the most straightforward or efficient solution to this problem -- but since you've already got working code here's a thought as to how you could evolve it. Check out some of the options in XML::Simple that control the way XMLin folds the generated data structure. Using keyattr, you ought to be able to set things up so that the data structure ends up with UID as a hash key. That would let you remove the loop that searches for the matching UID, something simple like this (untested, and dependent on your exact data structure):

$xref->{record}->{$newnode->{uid}} = $newnode;
[download]

Also, I would tend to avoid the four-digit zero-padded UIDs in favor of simple integers, which are less work to generate and also don't cause potential problems when you add your 10,000th contact -- though I hope that if you do have 10,000 contacts, you'd have begun using a real database rather than an XML file at that point :-)

        $perlmonks{seattlejohn} = 'John Clyman';