Almost same problem with Gmail, many of incoming mails go to SPAM folder without any notable reason =\
Yes, possible. in that case, Like I suggested in initial setup, you can actually contact your web hosting service, whether it's linux based or windows IIS. just request them to setup an SPF DNS. you can read details here on this website http://old.openspf.org/dns.html actually, it's out of my reach because I actually use google apps, but never had a problem.. and I think your friend is right about SPF records.. because when u use google (remote) service on your domain (hosted), sometimes, it could be the cause. hope that helps