Ok, dos cositas aquí, numero uno, estas describiendo una pesadilla para tú navegador, en especial IE es muy suceptible a paginas tan pesadas.
Segundo, estas haciendo una página que tiene más contenido en javascript que en el propio contenido de la página.
Sobre la solución te recomiendo altamente utilizar AJAX, yo sé que la palabreja te puede asustar, pero para tantos datos vale la pena.
Lo primero que te recomiendo es que hagas un script que genere un XML válido con los datos de tu base de datos dependiendo de el idpais enviado.
Algo asi como esto:
http://wifi.levhita.net/services/cities.php?idcountry=1
(te mandaría el codigo del primero pero va con smarty y un framework, asi que mejor te recomiendo seguir la estructura de resultados de este documento)
No olvides mandar en php "header('content-type txt/xml');" si no el navegador no lo reconocerá como XML.
lo segundo es que te bajes la librería prototype y comienzes a jugar con ella
http://prototype.conio.net/
Ya que andes por ahí puedes escibirme un correo y sigo con el asunto aquí en los foros.
Ha y por último tu pregunta inicial era más de javascript que de otra cosa.