Sounds Like a DNS issue. Resolvers outside the domain are looking at old ISP which are resolving to old IPs. See if you can update the MX records at the DNS levels to reflect the IP address change.
Where are the MX records located?
Internal DNS is working for domain clients, external clients are looking at MX records, which likely point to old IP address.