As you probably know, there are many reasons for email failure. It sounds like SOME of your email gets through but not ALL of it. I would start by inspecting the bounce messages from people who are unable to send email TO your domain. Perhaps they're using blacklisted mail servers, etc.

Since the majority of all email is spam, the mail hosting services I've used tend to be pretty aggro - denying mail from dynamic IP addresses, requiring reverse lookups, graylisting, etc.