No, al final lo de la url con un get lo he resuelto así:
Código PHP:
echo '<table><tr><td><table class="tabla" width="750px"><tr><td>'.$mensaje.'<br><form name="form" action="muro/eliminar.php" method="get"><input type="hidden" name="num" value="'.$key.'"><input type="submit" value="Eliminar"></form></tr></td></table></tr></td><br>';
Ahora sólo me faltaría lo de la función que elimine el mensaje con el numero que indica el get... Qué opciones tengo?