Send Mail From Web Form Using 3rd Party SMTP

I have a CDONTS script which has been sending mail from a client's website form to their address. However, the script has suddenly stopped working. It doesn't error, they just don't receive the mail. I've tried CCing myself in the script and the mail is not getting through. The script itself is tried and tested and syntaxially correct.

I think the problem is because they're using their own exchange server, not the web hosts' mail server. Therefore I would expect that mail sent from the web script wouldn't go through because there is no local mail server to process it.

The problem is that the script hasn't changed, the host say their system hasn't changed, and the client's IT team say their exchange settings haven't changed!

I could set up a CDOSYS script to use their Exchange server to deal with the email, but their IT support won't allow relaying, so I don't think this is possible.

Is connecting to their Exchange box the only option, or should the website host still be able to process the web-script-generated mail despite not being their mail provider? I'm getting a lot of grief here, but it can't be the script that has suddenly broken because nobody has touched it!