I have a Verizon 7750 (my second such model) and I have the problem that periodically I'll open the messages application and all of my messages prior to the most recent 20 or so and except for the ones I received on my first day of set up (welcome to blackberry, etc.) have been deleted. I am running 4.0 now but this also happened a few times before I upgraded. The messages are not deleted from the server when I log on to my PC, and the one saved message I have is not deleted from the blackberry inbox. Also, I didn’t have this problem before I broke the screen on my first 7750 and had to replace it. I do not think it could be delete prior because for it to happen inadvertently so many times I would have to be the unluckiest guy in the world. Any thoughts?

Check your free memory. It will delete the oldest messages first to free up space

Some of the BB users with 16 MB java models at my Firm are having the same problem. Doing a hard reset fixes the problem temporarily. I've also reloaded the handheld software, but only restored messages (no other databases) and re-activted the blackberry, which seems to have done the trick for most users.
The other solution has been to upgrade to 32 MB devices, such as 7100t, 7290 or 7520.

Where does it say that it will delete oldest messages first and how many does it delete at a time?

In addition to the BB deleting old messages to free up memory, the device may be set to keep messages for only a limited number of days. The settings in Messages/Options/General Options/Keep Messages range from just 15 days to unlimited. Might want to check that as well (this function will not remove those initial BB activation emails, which may explain why they are still there while more recent emails are not).