mmmmmmm tu post está muy confuso...... imagino que por que tu estas realmente confundido..... ok, segun entiendo! (no soy telepatico ni nad apor el estilo) quieres cambiar el titulo de la página por medio de ajax? y dices que solo te funciona una vez, cuando carga la pagina verdad?
bueno, por lo que comentas, lo que te hace falta es cambiar el titulo con cada respuesta AJAX que tengas, dices que para cada link hay que ponerle un titulo, entonces, cuando recibas la información del link que pulsaste, debes mandar tambien el titulo en la respuesta, por medio de XML o de JSON, dependiendo como estes trabajando hasta el momento, luego hacer esto
document.title = myJSON.titulo;
por cada respuesta recibida
have funnnnnnnnnnn!
pd: espero me entiendas, pues no se realmente que nivel tengas con AJAX, he omitido varias cosas obias!