Ben, most likely you're suffering a reverse lookup problem. To my knowledge, both Google and Microsoft require valid reverse lookups as to accept inbound e-mails. As stated above, youre HELO or EHLO needs to match your actual sending IP that in turn resolves when doing a reverse lookup. Check up on your own host and mailer, to see how it complies by using the DNS-Report at: www.dnsreport.com.
Also, you say you don't worry too much about inbound, - you should! If your mailserver is reported as an open relay, you will be treated as a spammer. Now, since you most likely only will allow SMTP connections from the very same machine, insert Allow 127.0.0.1 into connection control options of MercuryS module. Since we serve many domains, we nearly only allow authenticated SMTP connections to relay, meaning to check the last two boxes on Connection Control in MercuryS. Besides the authenticated, some internal servers are allowed within connection Control, all else is thus only allowed to connect with inbound email to local addresses.