It's not true, I've been working with Contabo for more than 2 years and I've never had problems with servers or emails, out of 6 IPs, not one is on the blacklist. I don't know to whom these things happen, it didn't happen to me.
And yes, there are also people who have never used Contabo's services, but they heard from somewhere or someone that it is bad, and they pass on erroneous information...