Sendmail: Sender address rejected (Domain not found)

This error is specifically regarding the 'from' address, not the sending mail server. As such, MX records are not relevant, and your MTA settings are probably not relevant.

The issue is that you're sending an e-mail from "[email protected]", which the recipient correctly determines cannot possibly be a valid e-mail address, since the debian70.vm domain does not exist.

The solution will depend on how exactly you're generating these e-mails. One option is to specify the desired 'from' address in whatever software is generating these mails.

On the other hand it looks like you're not actively specifying a 'from' address, but letting the system generate one. In that case, the part after the @ is set based on what the system thinks is its mail name. Debian checks '/etc/mailname' to determine this, and if it doesn't find anything then it uses its fully qualified domain name, which in your case is 'debian70.vm' - a name that's only valid for your internal network since it's in the .vm top-level domain.

If you edit /etc/mailname (creating it if necessary) to say 'premiumconnect.co.za' (without the quotes), it will probably solve your problem.

If not, then that could indicate that an MTA is generating the address based on some other configuration, so we would need to know more about your MTA setup.

How is it supposed to resolve the domain debian70.vm? looks to me you're using [email protected] as the sender address. The spam check is done over debian70.vm, which can't get resolved.

I found the problem, once I was pointed in the right direction by the other answers. The (autogenerated) sendmail.mc had a line MASQUERADE_AS(`debian70.vm')dnl, I changed this to MASQUERADE_AS(`premiumconnect.co.za')dnl and the emails are being set correctly now. Thanks for the insight.