Starting wih magento 1.9.1 all mails are added to a mail queued, you need program jobs for that, (I can do it)
This is a feature not a bug.
Also, if you don't have FQDN all your mail could be send to spam foders.. is a feature for mail servers.
I proposed you one technique:
a) Forward all your mail using your gmail account so local sendmail will be using gmail servers for outgoing mails
This approach is more efective for reduce this kind of mail into spam folder