Hola:
Mi opinión es que si se usa bien, debería ser igual su uso o no-uso, pero la tendencia con Ajax, por lo que estoy viendo es un mal uso.
En principio un sitio debe ser "navegable" con javascript desactivado, así que un enlace del tipo paginación, si las nuevas páginas entran con Ajax, pero existiendo el enlace paginado "?pag=n"... luego aplicas javascript cancelando ese enlace o ese submit, para realizar la petición con Ajax.
Pero como matizaba, la tendencia es usar Ajax para insertar distintos contenidos, sin usar enlaces ni botones de formularios.
Supongo que si usas Ajax (en mi opinión) correctamente, no debería existir ninguna penalización ni problema.
Esperemos otras opiniones, y cuando pase algun tiempo movemos el tema a Posicionamiento Seo, que supongo que sabrán más sobre el tema (sinceramente, yo me estoy interesando desde hace poco tiempo y mis opiniones tal vez no estén bien...)
Saludos
