Robartes, your suggestions led me to the answer. I didn't have access to the SMTP server, but found the person who does. The mail was reaching the SMTP box but was failing with an unknown user. Unfortunately, the guy couldn't explain why it ever worked before, but he did explain how to get it working. I had to change the extension @company.com bit to something slightly different and hey presto.

Thanks for your pointers, especially as this turned out to be a non-Perl problem.