smtp relay only works on gmail accounts

view story

http://serverfault.com – I have a client who has a server but does not host their own email. They have just purchased a MFC and want to scan-to-email. I have them set up to send mail to gmail, however if they try to send to an email address outside the gmail network it doesn't go through. I've racked my brain on this all day, what can I do? Thanks msindle (HowTos)