We are using 8830's at our company. We also are using a GPS program (3rd party) and started noticing that emails, SMS, and call logs would disappear after about 2 weeks. I spent 3 months on the phone with this 3rd party because we thought it was their software eating all the memory on the device. We also had Sprint and RIM on the phone for testing. Once we had a device lose all the memory...it was sent to RIM. After a month they finally said it was an issue with the OS that they have been working on....and not just with the 8830. It just so happened that this 3rd party app...really showed how big the problem was. Not sure when they will have the issue fixed. In the meantime...I have my users pull the battery daily to refresh the memory. The user may even notice the device hourglass for a bit while it tries to open any app....sure sign that the device is out of memory and fixing to clear the emails.

Lost messages and call logs is a longtime issue... here are to Sticky Notes that will help you deal with it...
http://www.blackberryforums.com/gene...-logs-sms.html
http://www.blackberryforums.com/gene...ee-memory.html

Did you consider this?

There are two key options to set on the BlackBerry unit:
1) Delete on: “Handheld” or "Desktop and Handheld"
2) Hide Filed Messages - Yes or No.

These two options work in conjunction to keep your BlackBerry Messages folder and Outlook Inbox as synchronized as possible.

Setting Delete on "Desktop and Handheld" works quite well. Regardless of which side (Outlook Inbox or Handheld) you delete the message from, after syncing, the message is in your Outlook Deleted items, and not in your Inbox or BB Messages folder.

If you have Hide Filed Messages set to Yes, and you move the messages from your Outlook Inbox to a Public Folder, the messages don't disappear from your handheld after syncing. If you move them to a personal folder under your own Mailbox, they no longer show up in your handheld messages folder after syncing (this is how it is supposed to work)

Just a thought!!! Sounds to me like messages are being hidden (Option 2). I have the same problem.