Yahoo blocked emails after changing mail server public IP address

We have two exchange edge server and we want to change their public IP addresses. Changing one of the server IP addresses (and related DNS records) was done successfully and emails are delivered to all destinations except yahoo which returns:

421 4.7.0 [TSS04] Messages from x.x.x.x.x(our ip) temporarily deferred due to user complaints - 4.16.55.1; see https://help.yahoo.com/kb/postmaster/SLN3434.html)

The other server could send email to yahoo without any problem. Our server and new IP address is not listed in any black list. I contact Yahoo and provide them information about the problem but they didn't give us any solution except their general recommendations. I post our problem here in hope that someone had this problem before and has a solution for it.

Edit: As we apply changes to IP and DNS configuration and revert them back several time during changing server's IP process we decided to use another public IP address to make sure it's not blocked because of those changes. Setting new IP address on server was fine at first and emails are delivered successfully but as we send 10 emails it start acting up again. The IP is being blocked for some minutes and is being unblocked again.

Edit 2: After setting the new public IP address on server, we continue being blocked by Yahoo for short period of times.One of our clients automatically send bursty email traffic to yahoo and this result in blocking by yahoo for about 30 minutes. I try to create a script to suspend those emails and send one of them to yahoo every 3 minutes.So far my script prevent from blocking by yahoo anymore.

Edit 3: As time past it seems the situation gets better and better and Yahoo doesn't block us immidiatly so I could reduce time between sending emails to 1 minutes or less without being blocked.

In many anti-spam systems an IP-address (range) will have a reputation that is either good, neutral or a known spam source.

By changing IP-addresses you lost your existing reputation and traded that in for the lack of or even the bad reputation established by the previous usage of that IP-address. (If the previous usage had established a good reputation your wouldn't be facing problems, right?)

Unless the recipients anti-spam system provides a method to reset your IP-address reputation you will continue to have delivery issues for a long time.

Like many providers Yahoo does provide senders a way to request such a reset of their IP-address reputation. See here: https://help.yahoo.com/kb/SLN24439.html