Lo mejor es eliminarlo manualmente pero también puedes probar con CWShredder. Es una pequeña aplicación precisamente para ese tipo de malware. Descargalo de aquí y actualizalo:
http://www.spywareinfo.com/~merijn/downloads.html
Por cierto, con firefox no pasan estas cosas. En cualquier caso, si no quieres cambiar el explorer, una vez removido el malware, usa el spywareblaster (
http://www.javacoolsoftware.com/spywareblaster.html). Esto te protegerá de posibles nuevos secuestros del navegador.