Eu recebi uma resposta no fórum Virtualmin que funcionou como um encanto.
Em resumo, o problema foi de fato em /etc/postfix/main.cf
, como sugerido pelas pessoas acima. Acabei comentando a seguinte linha:
#sender_dependent_default_transport_maps = hash:/etc/postfix/virtual
fez um service postfix restart
e agora meu e-mail funciona perfeitamente.
Obrigado pelos comentários acima e espero que isso ajude alguém no futuro.