Была такая же трабла, тока вылазили товары сексшопа

Или 1000 просмотров или 2 смс по 150 руб
Появилась эта х-ня когда брат решил чеерез спец. загрузчик скачать книгу
Вытворяет эти чудеса CMedia и FieryAds.
Удалил очень легко

Удалил C:\Documents and Settings\[имя пользователя]\Application Data\CMedia и
C:\Documents and Settings\[имя пользователя]\Application Data\FieryAds
еще в папке Application Data есть вроде cmedia.dat или fieryads.dat его тоже надо удалить. А так как эти программы внедряются в explorer.exe пользовался прогой
UnlockerДалее почистил реестр, введя в поиске "CMedia"
Больше ничего не появлялось

Можно еще глянуть в Program Files, там может быть FieryAds, его тоже удаляем Unlocker'ом