Ask Al: Blacklisted IP Address?

Tayo writes, "Our Outlook client suddenly stopped relaying mails with the error "Sending' reported error (0x800CCC78) : 'Cannot send the message. Verify the e-mail address in your account properties. The server responded: 550 5.7.1 This system is configured to reject mail from (IP ADDRESS) (Host blacklisted in uce3.dnsbl)' "

The IP address (IP ADDRESS) was traced to our ISP source. I think somebody blacklisted their IP Address. We called and they had been working on it since three days now with no solution yet.

Can you be of help? What can be done from ourside to solve this problem?"