Doch doch, in der Regel indiziert Google PHP-Seiten mit Parametern schon...
etwa diese >3 Millionen Session-IDs:
http://www.google.at/search?q=allinurl%3Aphpsessid
Wie "tief", dh bis zu wievielen Parametern Googlebot geht, hängt wahrscheinlich unter andrem vom PageRank deiner Seite, von der Ähnlichkeit der Seiten usw ab.
Man sollte darauf achten, dass die URLs wichtiger Inhalte zumindest nicht mit mehr als 2 Parameter enthalten.
Mod_rewrite oder andere Script-Tricks sind sicherlich empfehlenswert.
Der Grund für die Vorsicht der Suchmaschinen bei Query Strings ist, dass über Parameter alle möglichen Sachen passieren können, die keine Re-Indizierung rechtfertigen: Session-IDs, Sortierung von denselben Daten nach X Kriterien, Referrer-IDs, usw.