These are not the most scientific methods but they have helped me.
Try moving messages from the Inbox folder into their own folders (create more folders if necessary). Leave a max of 5-10 in Inbox, or move ALL if possible - this is just for troubleshooting purposes.
Also in OE, select File -> Folder -> Compact all folders.
If you still have problems let us know. G