Писал по интуиции - не тестировал



Суть в Encode::encode('cp1251', Encode::decode('utf8',...))


Можно, но это не даст того эффекта, что вы ожидаете.   

Хоть мне никто и не ответил... 
Но на самом деле, это помогло.
print MAIL "Content-Type: text/plain; charset=utf-8\n"; сразу после строки open (MAIL, "| /usr/sbin/sendmail -t");

Убивать сразу. Вообще, на почту и i18n в ней есть RFC, они несложно читаются (rfc2045, rfc2046, rfc2047, rfc2048, rfc2049), дополнительно для понимания общих механизмов можно просмотреть довольно муторный и пока вам неактуальный rfc2822, после прочтения стоит посмотреть в rfc-index на updates (которые для Вас тожэ не очень важны, на этом этапе).
Если не умеете читать -- то можно было хотя бы послать пример письма из известной почтовой программы самому себе, экспортировать на диск в какой-нибудь простой mbox, открыть его текстовым редактором и сделать своё в точности как там получилось.

Краткая выжымка: 

1) В заголовках письма при передаче (в т.ч. при передаче в sendmail) все символы должны быть 7-битные. Никакого utf-8 или 1251 туда печатать нельзя. Письма от людей, которые этого не понимают, получают у меня сразу 2/3 скоринга для отправки в спам (и это по-моему умолчание в спамассасине), а если пробираются ко мне -- то с неизвестных адресов сразу отправляются в корзину по причине нечитаемого subject.
Символы в нацыональных кодировках в заголовках кодируются методом, указанным в rfc2047. Например, можно каждое слово, содержащее что-нибудь кроме [0-9a-zA-Z] вместе с следующим пробелом заменяеть на строку =?utf-8?b?этослововbase64?= с пробелом после неё. Что такое base64 и где его берут в perl Вы, я думаю, представляете.

2) Большынство моих почтовых программ проигнорируют заголовок Content-type:, если не будет заголовка MIME-Version: 1.0
Добавьте.

3) Добавьте заголовок Content-transfer-encoding: 8bit 
Систем, которые без этого сломаются, а с этим воспримут -- ужэ очень мало, но во-первых, стандарт требует, а что Вам стоит, к тому жэ небольшой score в спамоловке можно себе скостить.