Una cosa simile, ho cambiato da SH404SEF sempre senza htaccess da index.php a index.php e Google, pur avendo già da un mese la sitemap aggiornata ha ancora indicizzate le vecchie pagine senza il "?".
L'unico consiglio che mi sento di darti è manda una sitemap aggiornata a Google e spera che i motori di ricerca non ti penalizzino troppo nell'aggiornamento degli indici.