Trulala de cordoba, te ayudaría si nos dijeras cual es la web que se le resiste a Google.
Por otra parte, nosotros esta semana hemos tenido un problema similar con dos webs de un cliente que no ciertas páginas no las indexaba google. El motivo, buscando en
www.forobuscadores.com encontré que a google se le atragantan las webs con más de dos variables en el URL, puede que estea sea tu problema también.
Por si a alguien le pasa, en forobuscadores.com dicen que las variables de paginación google las acepta así que puedes colocar 2 variables + la de la paginación.
Espero haber acertado con tu problema, sino pues muestra la URL y a ver si entre todos.