Не представляю, как можно сделать что-то подобное для обычного почтовика без расширений протокола. Ведь он должен общаться и с другими почтовиками, и они должны его понимать. Если сервер на входе принимает нешифрованное сообщение — то его в любом случае может прочесть хостер. Так же и в случае, если сервер должен переслать сообщение другому релею. Релей ведь должен будет принимать тоже нешифрованные сообщения.
Конечно, можно что-то накодить и уповать на то, что хостер не будет менять код, но это только иллюзия защиты, как и пункт в правилах соглашения о соблюдении конфиденциальности и неразглашении информации третьим лицам.
В общем, я вижу два варианта: написать новый стандарт почтового протокола и заставить всех перейти на него, или использовать шифрование GPG или любое другое.
Шансы реализовать первый вариант близятся к нулю, а при втором варианте слишком много почты будет приходить нешифрованной (особенно с сайтов с логинами и паролями), т.е., хостер будет располагать значительной частью данных.