Also, in "All Messages/Received", you might want to click the "settings for this view" button on the toolbar above the message list and check all the "show" boxes and search for the messages in question to make sure they're not just hidden.
Also, in "shift + F12 -> buttons -> mail/mail view", there's a period button/dropdown. Drag it to the toolbar above the message list. Then, open each message list and make sure the period is set to "forever'. If one or more views are not set to forever, that might be the problem.