Спасибо всем за высказанные мнения. Пока эксперементирую с фильтром sharpen(в Fireworks он тоже есть).
wvxvw
Если бы Вы поглядели файл который я выложил, то увидили бы, что этот параметр выключен для обоих картинок. Это то, что первое пришло в голову. Но он совершенно не влияет на описанную проблему. Так же я специально ставил картинки в целые координаты...
msdn
Потеря четкости совсем небольшая. Можно сказать, совсем незаметная. Я и сам бы не обратил внимание, если бы не сравнил две картинки.

Не думаю, что каким то способом можно качественнее уменьшить картинку, чем в редакторах специально заточенных для этих операций( Photoshop, Fireworks).