|"but our IP address was not black listed|
on popular a web site
The tool on that website doesn't necessarily check all existing blacklists, so your results there might be a false positive (or negative, depending on how you look at it).
This is actually pretty common. Often, entire blocks of IP addresses are blacklisted without regard for individual addresses within the block. This is an easy (albeit crude) method of blocking mail from ISPs who do or may host spam mailservers. Sounds like you might have gotten caught up in the dragnet.
The problem does sit with your hosting company, in that they own the blacklisted IP address block. You can request that your IP address be removed from a blacklist, but it will likely get re-added to the list eventually. And there are many, many blacklists.
Your best bet may be to use the VPS service, or find a co-location host for your mailserver.
Also, could you post one of the bounce messages for analysis? It's possible the bounce is not caused by blacklisting, which the bounce message should confirm or deny.