[exim] Best method to deal with rejects by Barracuda?

Every so frequently, I get users who complain that their emails are
getting rejected for unknown reasons by Barracuda. In almost all of
these cases, no blacklists apart from Barracuda indicates there was
any spamming/backscatter etc from the server in question. Since
Barracuda does not provide any hint or info on what/who might be the
culprit, there's no way for me to check/fix whichever user/domain that
might be.

The question is, apart from submitting to what amounts to a protection
racket/extortion in my opinion and paying Barracuda/EmailReg a yearly
fee to whitelist each and every single one of the server IPs, is there
any better way to deal with these incidents?