Changing platforms is not necessarily going to resolve your problem. When you say “the majority are complaining” what exactly is the bounce back they are getting? How are you handling SPAM filtering? Knowing the version and Service Pack level of Exchange would help greatly in troubleshooting your issue. Thanks.
If inbound messages are failing to be delivered, then you will need to provide us with with specific error messages the senders are getting back. Please also ensure that it is your destination system creating the error messages as it is possible that some intermediate host is failing during the message transfer and sending an error back to the sending system. Check your system event logs also to see if anything can be seen there.
Do you manage this system or are you a regular user?
In the IT trenches? So am I – read my IT-Trenches blog.