That's what I suspected. Outlook Express and Outlook are quite different programs. What you describe is not uncommon with OE. With OE closed try this:
Using the Windows Search function, search your hard drive for Pop3uidl.dbx. Be sure to include system and hidden files in your search. (If you're using Windows XP with multiple users, you should find 1 in each users profile). When found, delete the file (only for the user with the problem, if applicable). Then open OE. The messages will download 1 more time and then your 'remove after 5 days' should start functioning correctly.