What service is it, and why are they not allowing you to relay?
The spam filtering servers are local servers on our system. It's not an offsite service out in the world. The relaying denied messages are coming from the postfix daemons on the cluster, not from the filtering servers. The filtering servers are set up to accept outbound mail from the postfix system now. The problem is that I can't get the postfix system to send it to them.
Did you ask them for directions for enabling this? Or did you just try to use the same IP(s) that mail from them comes in on?
Yes. But the filtering servers are not the problem. They are not denying the mail; they are not getting it in the first place.