It looks like your DNS can't resolve the domains. Do you run your own DNS server? If not, your DNS provider may have changed configuration. Also, it may be worth checking to see if the recipients have been having problems with receiving mail from other senders.
If you have the time, you could run a packet capturing tool like ethereal to confirm that the problem is happening with DNS lookups.
The only other thing I could find by googling was related to the maximum number of processes allowed per user. Some setups have increased it from 128 to 512 and had the problem go away.
Last edited by gilead; 03-16-2006 at 08:07 PM.