Te aconsejo este tutorial de expresiones regulares:
http://bulma.net/body.phtml?nIdNoticia=770
El problema es que con (.*) incluyes cualquier cosa según he ido experimentando, a diferencia de Apache que sólo incluye caracteres alfanuméricos, incluidos espacios y </elimina>, esto colisiona con tu frase y salen resultados inesperados. Ahí va mi solución:
Código PHP:
<?php
$cad = eregi_replace("<elimina>([0-9a-zA-Z' ']*)<\/elimina>", "",$cad);
?>