I though the issue was with getting your mails accepted. Even gmail has no problem
sending email to a server that isn't properly set up as long as it is willing to accept.
Can you mention (or link to) situations where gmail refuses to send mails to another domain?