Thanks Jason. I copied your last reply to the hosting company, who replied:
We do not allow for scripts to alter the max execution time, this is set server wide to prevent any one user hogging resources. The time out is set to 60 seconds, most scripts should execute well within this limit.
If the current mailing system does not break these down properly into batches then you'd need to find an alternative solution that does, the way this script appears to work it needs to continue to execute until it has fully sent all emails rather than using a refresh to initiate the next batch which would start a new process for execution.
So I guess my question now is whether or not UE can break the emails down into batches?
If the answer is no, then it looks like our options are to either find an alternative to UE, or see if we can find a hosting company which allows UE to reset any time out limit.
Even if this wasn't possible by default, is it the sort of thing that might be possible as a custom, paid support ticket?