I've been having the same problem. I don't use Outlook, I use Windows Mail (Vista). My BB is deleting my inbox emails only, not SMS messages. It is even deleting saved email messages.
The free memory on my BB is 27 MB (27115644 Bytes). It's kind of low, but, I don't think it is at the "critical" stage.
My keep messages until setting is 30 days, similar to Skyguy.
One thing I do differently than some of you is that I turn my BB off every night. I think it gives a fuller charge by turning it off. When I turn my BB on in the morning, the previous day emails are gone.
I'll leave my BB on tonight (while it is charging) to see if turning it off is somehow causing the problem.
I hope someone could help me/us.