How many emails do you have in your inbox? I had errors like this when i had over 3,000 messages in my inbox. I just created folders and moved my messages out of my inbox.
Also what version are you using? Have you upgraded your Office to have all the vurrent updates? I know that Office 2003 has SP2 out. Maybe that will help clear up a few problems.