Not sure what mail service you are using, but sometimes a mail service only accepts a maximum number of simultaneous connections from the same server. I guess (not sure) the open connections are freed on a cf restart. If possible I would certainly look at error log of your mail server. I can't remember exactly but we had similar problems years ago. We solved that by sending it to some local server first and we tweaked the max number of outgoing connections of the local relay.