Long story short, that NDR report is either wrong& misleading or an indication of a fundamental problem in that mail server, it isn't caused by SURBL. You'll have to try to get that mail administrator to figure out what's going on. Good luck there, MS Exchange has a long history of Bowdlerizing internet-RFC error messages to "not confuse people". ;(
One other note, I've also seen issues where DNS servers were hammering the public mirrors of black lists that caused false positives like this. I don't remember what SURBL returns when it's blacklisted but it's a scenario to consider.
regards, KAM