Então é fixo, e é um erro noobish!
Eu deveria ter twigged quando eu estava recebendo o mesmo erro, mesmo que a porta 25 não estivesse aberta. Acontece .. Eu tinha uma regra iptables no seu que estava encaminhando para outro servidor. Então, a mensagem de retransmissão negada que eu estava recebendo não era mesmo do servidor eu pensei que era! Remover esta regra corrigiu o problema.