TDMWeb, Stormhosts, thanks for your suggestion.
After spending all last night and this morning going through every possible line of code and server config we can think of, we think we have the answer.
The code returning the error is a domain WhoIs lookup script that checks all the main domain suffixes, including a handful of .uk domains.
We think the error is caused by Nominet (The UK registrar) putting a temporary block on our IP address due to our site making too many requests to their database in one go. Apparently, they only allow you to make one search / request every 5 seconds. If you do, they block your IP for 60 minutes, after which you can try again. Our script is currently making 6 requests to their database in one or two seconds. Removing the .uk lookups allowed the script to run again.
We're now looking at ways of adding in a 5 second pause between each search or simplifying the domain lookup script to search just one domain at a go.
Fun fun fun.....