A simple vista, pareciera que ajax es totalmente incompatible con la indexación en buscadores, debido a que los crawlers (spiders) que utilizan los motores de búsqueda para recorrer la web y descargar las páginas que luego serán indexadas, no ejecutan código javascript, por lo que el contenido ajax nunca es accedido. La solución es justamente utilizar esto como herramienta, como no ejecutan javascript, podemos reemplazar los links de la página por llamadas ajax luego de la carga. Sería algo así:

1. Dejamos links absolutos a las paginas que generen ese contenido (estos links seguirán los crawlers).
2. Reemplazamos en el onload de la página todos aquellos links que queremos que en realidad sean llamadas ajax.

Por ejemplo, si usamos links ficticios con el rewrite de .htaccess (hay mucha info en la web) y llamamos a los links por ejemplo como www.dominio.com/contenido/categoria/pagina y queremos reemplazar todos esos links de contenido, el código sería así:

function cambiarLinks(){
 var menu = document.getElementById("menu_ID");
 var link_cms = "^(.)*/contenido/(.)*$";
 var links_menu = menu.getElementsByTagName("a");

 for(i=0; i<links_menu.length; i++){              
  if(links_menu[i].href.match(link_cms)){
   var req = links_menu[i].href.split(".com/");   
                        
  links_menu[i].href="javascript:cambiarPagina('"+req[1].substring(10,req[1].length)+"');";
  }
 }
}

Donde cambiarPagina es la función ajax que trae el nuevo contenido. Pueden ver como funciona en mi página personal: http://www.fernandohernandez.com.ar.

En mi caso solo cargo el contenido principal, lo único para considerar es que para todo lo que mostramos con ajax debe haber un requerimiento concreto que genere la mismo info, con una llamada absoluta, pero utilizando el rewrite por ejemplo es siempre el mismo script que toma el requerimiento como una lista de parámetros y genera el contenido deseado.