AJAX no es lo ideal para posicionar en buscadores, así que AJAX o no AJAX, sí deberías tener "PHP puro".
Ahora, los conceptos de "modular una web" y "tener que modificar en todas las páginas cada que cambias algo" no son compatibles, porque basta que pongas tus menús (y secciones comunes) en pequeños scripts (o funciones) que incluirás (o ejecutarás) siempre que los necesites.
De hecho, "modular webs" fue la estrategia para dejar de usar frames y, así como lo sugieres, AJAX sería regresar a esas viejas prácticas, cuando los objetivos principales deben ser posicionamiento en buscadores, usabilidad y accesibilidad.
Por cierto, hace algunos años hice un tema sobre webs modulares, nunca lo he actualizado, pero te puede servir para darte una idea:
http://www.forosdelweb.com/f18/aport...ulares-681437/