Relaying Denied error in MS Exchange

Last week our ISP notified us that we were sending spam mails. So we configured our MS Exchange 5.5 to stop relaying. (Authentication is required and no hosts nor IP addresses are allowed to relay). Now our email can get in but outbound mails are returned with a “relaying denied” message. However, if we sent an email to our ISP’s domain, it gets thru. Our ISP contends that the fault is with our configuration, while our MS Exchange vendor claims that the error is with our ISP’s configuration. I tend to agree with our MS Exchange vendor, but how do we convince our ISP? Thanks.