В общем, нужен MDA, который в дополнение к возможностям procmail умеет сам распаковывать MIME-кодированные заголовки в Unicode и делать сопоставление с ними.
Procmail пытается сопоставлять заголовки в исходном виде =?UTF-8?B?bla-bla-bla?= и это, естественно, не работает.
Всяких MDA много, на тестирование всех уйдет уйма времени. Если кто сталкивался с подобной проблемой и уже знает подходящий ответ, поделитесь, pls.