After some further investigation in turns out the reason for receiving the smtp errors was that
I was blocking all outbound traffic to port 25 via virusscan. Disabling this solves the problem.

Setting up the primary dns server is still not solving the smtp error. I have access to 2 DNS servers, and making either of them the primary DNS in sequence still doesn't locate the smtp server.