Методом тыка новыми кодировками в этот несчастный браузер установил что, для браузеров от Microsoft нужно использовать windows-1251.
UPD: Наврал.
Метод, которым php проверяет кодировку работает неверно. (mb_detect_encoding()). Методом тыка выяснил реальную кодировку - windows-1251. И через iconv изменил кодировку куки на UTF-8
