I have been trying to set up Mail Server, I have the internal mail working fine... but can't get the external relay working.
This is the error message that comes up 'Name service error for name=smtp1.tnz.mail.vip.aue.yahoo.com type=MX: Malformed or unexpected name server reply'
Can anyone point me in the right direction at least!
Your domain name is Feast.co.nz so your host name should probably be somehost.feast.co.nz or simply feast.co.nz as well. Make sure it has DNS reverse resolution in place.
Coming back to your issue, try and send a couple of mails and post the relevant log entries.
Single log lines are useless. This could just as well be an entry while you were restarting mail services.
Always make sure log entries are in a context.
If the mail server wasn't running at all, you wouldn't even be able to send internal mail.