Setup proper SPF records for your domain(s) for one.
That's supposed to help with what regarding his problem? OTOH I have no idea which problem SPF solves anyway other than making it harder for others to use your domain for fake adresses (if receiving mail servers do some sort of check against SPF).
Ralph
I think google/gmail pays attention to it and they add points for it.