Hola,
tendrias que haber hecho esta question en el foro de buscadores, pero bueno, te contesto igual
Google lee las paginas dinamicas de tu web, no asi msn. Sin embargo, una de las cosas que se aconsejan para salir en la mayor cantidad de buscadores es aplicar lo que tu indicas (mod_rewrite).
Aun asi google, buscara todas tus paginas si le generas un sitemap. Si quieres hacer uno, vete a la pagina:
https://www.google.com/webmasters/sitemaps/login
alli te explicara como generar uno. De esta manera, generaras todas tus paginas de la web y se lo indicaras a google mediante un fichero xml.
Tendras que registrar una cuenta. Una vez dentro, te explicara como generar uno.
Ahora bien, si quieres mas info sobre buscadores, vete al foro de buscadores y fijate en las faq, de seguro te soluciona muchas dudas
espero te sirva
