Email from my server rejected because of ISP's IP blacklisted

I'm going to guess that the recipient mailserver's mail is collected by a Barracuda Spam Firewall with "Deep Scanning" turned on. Deep Scanning on a Barracuda yields so little improvement in spam detection on the Barracuda device, and it generates a lot of false positive blocks [such as in situations like yours] that Barracuda should not even include the deep scanning option. And any mail administrator managing a Barracuda Spam Firewall should consider never enabling Deep Scanning.

My suggestion [although a pain to you and your clients] is to contact the recipient mailserver admins [or have your clients do so] and suggest to them that they need to turn off Deep Scanning on their Barracudas because they are doing their own customers [and potential clients attempting to email them] a huge disservice by [inadvertently] blocking legitimate emails. A real email admin knows how to properly configure a Barracuda Spam Firewall. If you contact those companies and their Barracuda admin doesn't want to disable deep scanning, he should be fired.

The Barracuda Spam Firewall is a wonderful device, if configured properly. If configured with Deep Scanning, it's a piece of garbage that blocks a lot of legitimate email.

NOTE: It is only a guess that the recipient mailsystems that are blocking emails from your client are using Barracuda Spam Firewalls, but I think it's a good bet that they are.

Mike