Cannot retrieve mail after restart

XServe G4 running 10.4.8 hosts mail for 6-person Mac network; users use Apple Mail to retrieve either via POP (their own accounts) or IMAP (to check each other’s accounts). Not sure if this has anything to do with it, but Monday 3/5/07 we used Apple Software Update for QuickTime and iTunes; since then, every time the XServe restarts, no one can retrieve his email (although mail can still be sent out).
The XServe generally restarts automatically during the night after it is backed-up by Retrospect. Prior to Monday’s Software updates we never had a problem retrieving mail the next day.
Since Monday, I’ve had to stop then restart the Mail Service and then do a “Retry” on the mail that’s accumulated since the nighttime restart, still sitting in the Mail Queue. Once “goosed” through, the Mail Service acts normally the rest of the day… until the next XServe restart, when the problem recurs.
Any info or help greatly appreciated!
Bob A.