Ho trovato la soluzione.
La posto nell'eventualità che possa servire a qualcun altro.
Piccola premessa: la soluzione che ho trovato (relativamente semplice) si basa su dom e non su simplexml.
Codice PHP:
if (file_exists('./ips/'.$ip.'.xml')) {
$doc = new DOMDocument();
$doc->load('./ips/'.$ip.'.xml');
$padre = $doc->documentElement;
$xp = new DOMXPath($doc);
$query = $xp->query("//message[@id='".$id."']",$padre);
$node = $query->item(0);
$old = $node->parentNode->removeChild($node);
$doc->save('./ips/'.$ip.'.xml');
}