Ok Ho provato ad inserire come dici tu, un valore random ma non funziona lo stesso, ho fatto in questo modo dimmi se ho sbagliato:
xmlhttp.open("GET","lista_comuni.php?prov="+str+"& rnd="+Math.random(),false);

questo il codice completo.
http://codepad.org/WSVJj5Zu
quali potrebbero essere gli errori, che non fanno funzionare il tutto su internet explorer???