Pourquoi ne pas prendre un serveur dédié que vous aurez libre choix d'administrer vous-même ?
C'est peut-être une solution, reste a voir le surcoût lié à cette solution.
Sinon si vous possédez des lignes louées, vous pouvez très bien héberger vous même votre serveur de messagerie, peu de ressources sont nécessaires et de nombreux serveurs de mails simples existent.