Hola!
1) google sí las indexa, ese tipo de urls:
http://www.google.es/search?q=%2F%3F...ient=firefox-a
2) otra cosa es que le cueste más, o que no sean amigables, y menos, semánticas (que sería lo más recomendable de cara a posicionar: tener palabras clave en la url)
Nunca había oido de un script para hacer un cambio/redirección de las url... lo más usual, es hacerlo mediante .htaccess. Busca en google por url amigables mediante .htaccess y verás bastante información al respeto!
Saludos