DJ PhoeniX, низкий тебе поклон.
Дошли вот руки до решения этой проблемы.
Нагуглил конверт из 866 в 1251, полчаса повозился с его применением и всё решилось =)
Как вспомню сколько часов я мучился, решая эту проблему со стороны MySQL'а - становится грустно.
На производительности, конечно, такое решение скажется... но если учесть, что заказчик тестовый вариант ждал позавчера...