Cambiare i link direttamente in statici nel template perchè parsare tutto il codice html sarebbe molto molto dispendioso.

Inoltre devi cambiare proprio la struttura dei link. Tu usi il ? che è quello che dà problemi a google. In questo modo vanifichi l'uso del mod_rewrite. Se invece utilizzi un link tipo tuohost.xx/var1_val1-var2_val2 ottieni lo stesso risultato ma inganni il motore di ricerca.