Para futuros pesquisadores sobre esta questão, é possível ter o postfix (ou qualquer outro servidor) em execução, mas especificamente não escutando no host local. Pode ligar-se a endereços individuais que não são localhost.
Se a saída do netstat diz algo diferente de * .25 ou 0.0.0.0:25, há uma boa chance de você estar ligado a qualquer interface que estiver rodando e você terá que fazer telnet para aquele IP (que ainda é local!)
Em outras palavras, localhost não é o mesmo que o IP em execução na sua máquina.