Information for other experts: I was asked to not reveal details, but I still wanted to answer it here - it can still be helpful for other EE users (I hope :)) even without concrete domain/hostnames.
So - I checked MX's for your.domain.name, and it looks, that you are using external company's SMTP to receive your emails, which are later relayed/forwarded to your own SMTP.
For "host -t mx your.domain.name" command I got answer:
your.domain.name mail is handled by 10 10smtp (real name hidden :))
your.domain.name mail is handled by 20 20smtp (real name hidden :))
your.domain.name mail is handled by 30 30smtp (real name hidden :))
your.domain.name mail is handled by 40 40smtp (real name hidden :))
your.domain.name mail is handled by 50 50smtp (real name hidden :))
Your new smtp server has lowest priority (50), so as long as previous ones (10smtp, 20smtp, 30smtp, 40smtp) are working, it will not receive any email (theoretically - some spammers are often sending their emails through MX's with lowest priority, but it's not the case right now).
You are pointing your main MX's to external company's SMTPs, so you should tell them, that your own SMTP server has changed, and give them its new IP (or - if you have access to some configuration panel, change this by yourself). I don't know this external company, and I'm not familiar with services they are offering, but it looks, that they are not aware of your server's IP change.
Other solution could be to change priority of your SMTP server (the one with new.ip.address) to 0, but then you will of course miss features offered by external company.
Hope this helps