Hola,
Las capacidades de los robots de los buscadores para entender javascript, flash, applets, etc son bastante limitadas. Los enlaces hechos con HTML directamente seguro que los entienden todos.
Cita: En caso de no ser así, ¿se os ocurre algún truco para hacer que puedan rastrear esos links sin tener que reescribir todo el menú?, por ejemplo tags ocultos o algo así...
Tags ocultos no, contenido alternativo. El standard HTML dispone de mecanismos para ofrecer contenido alternativo a los navegadores/useragents que no soporten algun tipo de tecnologia. Asi que asume que los robots son navegadores sin soporte javascript ni flash, y usa los mecanismos de HTML para ofrecer contenido HTML alternativo. En
www.w3.org en la seccion de HTML, en el standard, encontraras como hacerlo.
Saludos.
PD: ¿Verdad que me enrrollo demasiado sin darle la respuesta exacta? Podia darsela en 4 palabras, pero me gusta verlos sudar buscando la respuesta