Ian,
Are you on a Plesk server?
The single most important thing you can do on a Plesk server, or any server having troubles with timeouts, is disable PHP safe mode for the domain.
In Plesk 8+ you can do this from the Domains "Setup" page within the Plesk control panel.
In previous versions of Plesk the following must be entered into the file:
/var/www/vhosts/example.com/conf/vhost.conf
<Directory /var/www/vhosts/example.com>
php_admin_value safe_mode 0
</Directory>
Note: Replace "<" with "<" in the quoted code above...
Then restart the Plesk back-end like this:
/usr/local/psa/admin/bin/websrvmng -a -v
Note: /var/www/vhosts could be /home/httpd/vhosts or other on some servers.
Please let me know if you continue to have mailing errors - perhaps I can help further.
Regards, DW