Praticamente qualquer ISP satisfará essas necessidades, mas você terá que pagar por isso.
O que você essencialmente precisa fazer é configurar um MTA local (por exemplo, exim ou postfix) para executar no modo smarthost, onde ele encaminha todas as mensagens para outro servidor de email (o servidor de email do ISP). Seu servidor de e-mail local seria configurado para não retransmitir nada além de mensagens de sockets locais (que é a configuração padrão para o exim). Isso evitará qualquer uma das dores de cabeça que você deseja evitar.
Como você está realmente enviando e-mails através de um MTA local, você pode usar a biblioteca PEAR para PHP para fazer isso (funciona muito bem e suporta diferentes domínios e endereços "FROM", diferentemente da função padrão de correio PHP). Isso também suporta mensagens de texto simples e mensagens em HTML (provavelmente úteis pelos sons da sua pergunta).
Você terá que obter uma conta de e-mail para cada domínio individualmente (pelo menos com a maioria dos ISPs que eu conheço). Se você não está feliz em pagar por isso, então eu tenho medo que você terá que executar o serviço de correio você mesmo (com todas essas coisas que o acompanham).