Exchange Srever 2000 / Outlook Sync

About three times a day the Outlook clients on the network I administer ‘lock-up’ when sending mail. The mail stays in the outbox. When I check the mail queues they are empty. Where does the mail go if it has left the mail queues, but the Outlook clients don’t update until a server re-boot? Then the mail in the outboxes goes. Is the mail still in each user’s? mailbox. How do I fix this. My client relies on e-mail, & I’m getting a lot of flak