Podés probar realizando una limpieza con este soft:
http://download.iobit.com/asc-setup.exe
Y lamentablemente Internet Explorer no es tan seguro como Firefox u Opera, así que aunque quites las publicidades no pedidas, es mayor la probabilidad de que vuelvan a aparecer con el navegador de Microsoft.
Puedes disminuir el problema de pop-ups con algún programa que controle el tráfico por Internet como ser Kaspersky I. S. pero no son infalibles estos métodos.
Lo que queda es mirar bien donde navega uno y usar otro Explorador que no sea el centro de ataques tanto como IE.