Use an XML parser, like SimpleXML. Regex isn't made to do XML/HTML parsing, and here's a perfect explanation of what happens when you do: RegEx match open tags except XHTML self-contained tags.
Parse the input as XML, use the parser to select the required elements, edit their properties using the parser, and spit them back out.
It'll save you a headache, as regex makes me cry...
Here's my way of doing this (didn't test it):
<?php
$xmlString = "This is where the HTML of your site should go. Make sure it's valid!";
$xml = new SimpleXMLElement($xmlString);
foreach($xml->getElementsByTagName('a') as $a)
{
$attributes = $a->attributes();
if (isThisExternal($attributes['href']))
{
$a['rel'] = 'external';
}
}
echo $xml->asXml();
?>