A melhor maneira de conseguir isso seria do firewall. Configure uma interface para ambos os ISPs com um mx diferente apontando para o respectivo IP público. Adicione uma regra SNAT para a porta 25 ao servidor do Exchange de ambas as interfaces externas (duas regras separadas). Você está certo de que precisará de dois registros MX e o secundário deve ter uma prioridade maior que o primário. Agora, sem configurar o failover para o (s) seu (s) firewall (es), ele ainda é um ponto único de falha, mas o firewall HA é completamente diferente.
Para evitar colocar listas negras e outros problemas de envio (isto é, servidor SMTP remoto recusando conexões), você deve fazer com que seu ISP crie um registro reverso (PTR) para seu IP secundário. Se você usa um serviço como o No-IP ou o DNSPark como seu provedor de DNS, poderá fazê-lo sozinho, mas é melhor que o ISP faça isso.