Cita: Podría meter todos los enlaces en una misma tabla, añadirles un campo adicional para especificar a qué categoría corresponden
En el ejemplo que te mande tiene para realizar el menu con submenu, todo en la misma tabla, que es lo que inicialmente habias dicho pero que tenias un inconveniente:
Cita: El problema es que en ese caso debería especificar de antemano cuáles serán las categorías que crearé, y escribir tantas consultas como categorías haya. Si más adelante decido añadir una nueva categoría, tendré que modificar la consulta.
Pero te fijaste en la pagina que te envie como el autor del ejemplo resolvio el problema?
Mira el resultado de la funcion:
http://tmferreira.pandela.org/menu/index.php
No se si eso es el resultado al que quieres llegar.