Alguns servidores de e-mail suportam vários certificados no mesmo endereço IP, mas precisam de um cliente ciente de SNI para que o certificado adequado possa ser fornecido. Nem todos os clientes suportam o SNI, então você não pode confiar nisso.
Isso significa que você precisa viver com um único certificado no seu servidor de e-mail. A maneira mais fácil seria configurar o MX para os domínios do cliente para apontar para este servidor securemail.hostdomain.com e não para mail.theirdomain.com como você faz atualmente.
Se você não quiser fazer isso de maneira simples, precisará de um certificado de vários domínios que inclua todos os domínios que você deseja veicular neste servidor. É claro que é necessário que você realmente possua todos esses domínios ou pelo menos tenha acesso suficiente para reagir ao desafio usado na validação do certificado de DV. Se esses domínios estiverem em total controle do cliente, você não poderá fazer isso.