The fact that you are still receiving emails from outside your organization says that your servers are not the problem. Remember that when it comes to DNS, any changes need to be propagated around the entire World! This takes time, up to 5 days in some cases. Anything that goes on longer than that are going to be be smaller entities that do not update their servers on a very timely basis.
The only solution is to wait it out.