На самом деле всё очень просто. И поможет нам imap-протокол для доступа к электронной почте.
1. Настраиваем почтовый клиент (например, thunderbird) для взаимодействия с почтой через imap.
2. Выполняем синхронизацию, клиент закрываем.
3. Локально меняем нужные данные в теле письма (и адрес отправителя, и дату, и всё что хотим).
4. Удаляем на сервере (через web-интерфейс) наше письмо.
5. Запускаем почтовый клиент, выполняем синхронизацию.
Только что проделал это со связкой thunderbird+outlook.com. Метод работает.