По-моему еще важную AJAX-проблему упустили из обсуждения, впрочем она скорее вытекает из тех же проблем навигации.
Это — индексация AJAX-ресурсов поисковиками. Кроме как решения на основе "спам-страниц" ничего больше особо мне и не встречалось
Лично для себя я определил такой "отправной" алгоритм выбора:
AJAX-для интранет (внутренних) ресурсов
без AJAX — для внешних информационных. + во внешних, AJAX оправдан в плане ускорения работы контролов которые не являются средствами отражения информационного контента.
Естественно, это не какое то жесткое правило и компроммисы, в принципе, вполне возможны.

p/s/
news по теме :

Yahoo не стал сайтом-лидером США по количеству запросов интернет-страниц в ноябре. Причина этого – внедрение технологии AJAX, позволяющей обновлять веб-страницы без перезагрузки.
Забавно. Видимо в Yahoo начали искать крайних за маркетинговые провалы, и нашли их среди разработчиков. Хотя выглядит это не очень убедительно. Я, специально походил по Yahoo и нашел AJAX-овые компоненты только на главной странице. Вряд ли они могли кардинально повлиять на статистику сайта, которая насчитывает десятки миллиардов посещений.
С другой стороны проблема все-же существует. При использовании AJAX запросы на сервер все равно идут, но посколько они направлены не к обычным web страницам а к web сервисам, разместить на них обычные счетчики невозможно. И этот трафик действительно оказывается не охвачен статистикой.
Я думаю системы оценки и ранжирования сайтов ждут большие премены. Ведь место в рейтинге это большие деньги и их никто не хочет терять.