Si te funciona tal y como te recomienda Óscar pues genial. Pero yo te habría respondido de otra forma que, si es que funciona (que creo que debería) me parece más simple.
Cuando muestras el formulario de HTML, pregunta primero si no ha sido pulsado el botón, y muéstralo sólo en este caso. Así, justo debajo de echo $mensaje:
Código:
if((!isset($_POST['eliminar']))){
?>
<!-- creamos el formulario HTML que enviara el ID del registro a eliminar -->
<form name="eliminar-registro" method="post" action="<?php $_SERVER['PHP_SELF']; ?>" >
<input name="id" type="hidden" value="<?php echo $row['id']; ?>" />
<input name="eliminar" type="submit" value="Eliminar" />
</form>
<?php
}