I presume that all other mails are going as usual except sent to some particular domains say hotmail or msn, and they go only after the rebooting of mail server. one important question in this regard is – is it happening for all internal mails that go without rebooting and for external mails it is requiring rebooting or is it happening for only few external domains. Most probably your smtp is not able to shake hands properly with your mail service provider’s server that is being used as a gateway to shoot external emails. Also it is important to know that if in a queue of mails to be sent if there are mails below a mail to be sent to say hotmail, then are those going are they also get stuck up. The exact solution will depend on these issues. Check your outgoing policies for mails in exchange. You have to check the internet status also. Try pinging your external smtp server IP, if it is giving some RTOs or not.