решается проблема интересным образом: вместо реального названия сайта, написанного на кириллице, нужно использовать его punycode вроде xn--90azcerm.xn--p1ai
таким образом, при отправке письма функцией mail() в параметре отправителя указываем no-reply@xn--90azcerm.xn--p1ai - письмо приходит в правильном формате, в поле "От кого" указан кириллический адрес.
Но вопрос в другом. Например, если смотрим письмо в веб-интерфейсе mail.ru, то в списке писем адрес показывается как есть (без конвертации в кириллицу) no-reply@xn--90azcerm.xn--p1ai, а вот когда открываем письмо, то там уже с конвертацией. Я думаю, это баг mail.ru, на других почтовых сервисах пока не тестировал. Но теперь другой вопрос - эстетического плана - нужно как-то добавить имя отправителю, чтобы в списке писем показывался не голый адрес, а какое-нибудь произвольное название... Ну, это уже нагуглю.