The best way to fix it is to authenticate your Google Apps Account using SPF (Sender Policy Framework). Using SPF recipient’s mail server verify that which server is sending email and whether its allowed to send mail on behalf of Domain or Not.
Open your domain control panel and navigate to DNS records setting, we need to add a new TXT records to your domain and set it value as :-
v=spf1 include:_spf.google.com ~all
Server will take 3-4 Hrs to take effect, after that you can check whether your effort has been successful or not, to check SPF records of your domain do this :-