ICЕ LiM
Дело в том, что эти "шайтанские" прокси - это прокси моего провайдера. Так что с ними по идее должно быть все в порядке.
Эта загадка решилась сама собой. Спустя пару дней мой explorer снова стал видеть прокси. Я ничего не делал... Что это было? А, бог его знает... Может непорядки у провайдера, может еще что...
В общем все работает.