Thanks Mags.. It was indeed Spamhaus that had blacklisted our IP address. I discovered it when I ran a send mail script in debug mode and the log results gave us the problem. I will look to set up a PTR record as you mentioned.
Your friends over here at WebAssist! These Dreamweaver extensions will assist you in building unlimited, custom websites.
These out-of-the-box solutions provide you proven, tested applications that can be up and running now. Build a store, a gallery, or a web-based email solution.