Calendaring issue in Outlook, causing several quirks

We have had outside people suggest it's a problem with our Exchange Database, but all they can suggest is asking Microsoft for a custom service pack. Please take a look of the symptoms we are experiencing.  We're running Exchange 2000 SP3 on a Windows 2000 Server, all clients are running Windows 98SE and OutlookXP.

I'd like to know what type of problems might cause behavior like this, I know that not all these may be related to the same problem, but I'm not sure which are tied to the which problem.  
Here are the symptoms

One User sent an ALL DAY EVENT which covered the time span of 4/9 through 4/14 to five people in her group. (Start date: 4/9/03 End Date: 4/14/03.) All five invitees accepted the event. When she went back to check to see if it was there, it appeared on the calendars of three of the five for all six days; however, on HER calendar (as well as her proxy's calendar), it only appeared as 4/11 through 4/14. Also, when she checked the tracking status, it showed only that two of the invitees accepted it, when, in fact, all had. The two that it showed were the two that had accepted without sending a response.

People are sending invitation appointments to distribution lists on a particular day. When they come in the next day and add someone to the invitation list and select the option to send to the new invitee only, Outlook deletes the appointment from everyone on whose calendar the appointment was posted other than the new invitee.

One User made a rule for certain incoming messages to be moved to folders and marked as read; they're getting moved into the folders just fine, but they're not getting marked as read.

One User calendared an event and invited another. She has the "accepted" message from him in her inbox. The properties for that message show it was received and accepted by him; however, the invitee told her that it was not on his calendar.

One user also calendared a bunch of Tasks for a group of users. She can pull up someone elses calendar and see all the tasks there, but only a few of them show up on HER task folder. The ones she's missing are also missing from her "Sent Items" folder. She has no record of ever having sent or received, except for seeing them on that other users calendar.

One user says that sometimes his "today" list will show activities that are in reality "tomorrows." It usually happens when there are no activities for the day.