Your problem really seems to be DNS related. I would use the tools at www.dnsstuff.com.
Just running the regualr DNS Report it will check a number of areas that your DNS settings could be wrong. Pay close attention to the MX portion or the report, to see if anything doesn't pass. Steve Belt
