Hi,
Sounds like you have done what you can on your end. The owner of the domain would have to work with the hosting company to get the domain/IP range checked to be removed from those lists. But, that may not change the behavior, or if it does, only temporarily. I went through this with an old hosting company for years and it was never permanently resolved.
C