Yo vivo aquí y como vegetariano sólo conozco el Sarasate. Pero en muchos sitios (vaaale, en unos cuantos y de la zona donde vivo, pero supongo que pasará igual en otras partes) si llamas y les avisas antes te preparan un menú vegetariano. No los suelen tener en menú o en carta porque aquí no se lleva mucho, pero me imagino que entre peregrinos y turistas (y algún autóctono), los cocineros se están haciendo. Y por cierto, cosas muy ricas.
Conclusión: que es mejor que llames y avises y en muchos sitios te pueden preparar algo. Eso sí, especifica lo de la leche y el huevo (si no los comes) para que no se lien y te lleves alguna sorpresa