Send Email Through Web Form, Using External 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 after three years of working fine. It doesn't error, they just don't receive the mail any more. I've tried CCing myself in the script and can confirm the mail is not getting through. The script itself is tried and tested and syntaxially correct, and it is hosted on a windows 2000 server which has not been changed or reconfigured at all recently.

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!