How to resolve 'HELO/EHLO outbound.qs.icloud.com is not matching your DNS configuration' error in iCloud Mail?

HELO/EHLO DNS Configuration, Mail doesn't deliver email to specific address

Mac OS 15.4.1 / iPhone 18.4.1

I cannot send email via Mail iCloud to one distinctive email provider. The emails bounce back after hours with this msg: "refused to talk to me: 421 EHLO MXIN201 Your HELO/EHLO outbound.qs.icloud.com is not matching you DNS configuration"

This happens when I send email via iCloud with wifi on. If I send it thru my iPhone mobile service (wifi off) the email reaches its destination 100%. Also, I can reach it thru gmail or outlook accounts. Strangely enough I can reach my iCloud address from that other email address no problem. Even more strange: I can send email to that email address using iCloud webmail.

I have spent hours talking to Apple Support and the provider, to no avail. The provider says it's an issue with iCloud. Apple says it's a problem with the provider.

I have checked ALL settings (osx mail, system, router) and cannot find any problem. All settings are as expected. I have latest software on all devices. I have switched off all security software (Norton). This issue started after I installed OSX 15.4. but I doubt that this is the problem.

[Re-Titled by Moderator]