My domains are hosted by United-Domains.de, my mail box and web space are hosted by another provider.
Provider#2 uses an RBL list, which has a “bad reputation entry” concerning the SMTP server of provider#1.
This is how I finally understood my situation today, after having suffered from e-mails getting bounced for quite a couple of months. What a luck, provider#2’s hotline isn’t any expensive at all.
I had a calm and relaxed conversation with the highly experienced supporter at the other end, and he explained me how to remove the RBL checking for my e-mail addresses. He warned me to do so, because that would increase the amount of SPAM arriving at my account, but I praised their SPAM detection and flagging of the e-mail headers and also my own procmail rules.
Now, I am very positive, my suffering found an end.