Embaraçoso, mas é melhor eu fechar essa questão. Os problemas estavam com o meu servidor como eu tinha configurado o nome de domínio do meu cliente como um nome de domínio estacionado. Quando eu enviei e-mail usando o meu servidor, ele olhou para as contas de e-mail localmente (eu esqueci que isso aconteceu), mas eles estavam hospedados em servidores diferentes. O email deles não tinha quebrado como eu pensava. Alterar os dois registros A, como descrevi originalmente, fez, de fato, os redirecionamentos necessários.