If mail is sending to other domains like Gmail and Hotmail, then it doesn't sound like an issue related to Magento sending mail.
Here are a few ideas:
1) If you're able to send mail to other domains, but messages sent to your own domain(s) don't work, it could be a mail server setting. For instance, if your web server is set to deliver mail locally (MX Records pointed set locally on your web hosting server), but your e-mails are hosted on another server, then your web server could be trying to deliver mail to itself, and failing, since you don't manage e-mails on your web server. I've seen this happen dozen of times over the years. I would check with your web host to see if the server is properly set up to send mail to whatever server you host your emails on.
2) Your domain or IP address could be on a blacklist used by some mail providers, and not others. This would explain why some domains receive your messages, and others don't. There are lookup tools https://mxtoolbox.com/blacklists.aspx and http://multirbl.valli.org/ which can be helpful to see if you're on any major blacklists.
Best of luck!
