Hola, mira, a mi parecer, tu problema recide en que cuando "desinstalas" illustrator, no se desinstala completamente, lo que pasa, es que por experiencias propias, me ha pasado que intento desinstalar illustrator y el programa de instalacion me marca , o que se desinstalo correctamente, o que hubo un error al desinstalar, en fin, yo he sulucionado el problema de la siguiente manera
1, si tienes el cache con propiedad de solo lectura, es mejor que lo borres ya que habra problemas al desinstalarlo o querer instalar otro programa adobe. ya que ahi se guardan los datos de activacion
2 - si el programa de instalacion te dice que la desinstalcion ha finalizado corractamente, revisa en la carpeta de instalacion en C:\Program Files\Adobe\Adobe Illustrator CS4 . Si sigue ahi, borrarla directamente, ala fuerza, despues le pasas un limpiador de registro, algo asi como Free Window Registry Repair , o si quieres el del ccleaner, ( te recomiendo el free windows registry repair, es mas profundo)
3- Si tienes algun otro programa adobe que te de el mismo problema, desinstalalo de una vez, y siempre deja en ultimo lugar la instalacion de Illustrator
4- Reinstala illustrator y los demas programas adobe , en caso de que asi sea, ya que por lo regular siempre usan photoshop e illustrator, deja la instalacion de illustrator al ultimo
5- Comprueba despues de reinstalar si funciona illustrator, ya con el amtlib.dll instalado y el cache que deje mas arriba.
Yo estoy seguro que con esos pasos deberia de funcionar, si no es asi , posteas de nuevo haber si te puedo ayudar
Suerte !!!