We noticed that CMS documents and folders disappeared from the CMS when we booted out portal that had been running for a few weeks.
This only affected a few folders and files.

How is this possible? I mean where was the data stored (it's not in the database, I checked)?
Is it stored in memory in some weird hibernate cache or what's happening here?

I tested this again by adding a few files and folders and then booting and nothing happened, so this doesn't occur all the time. I have not yet tracked down how to reproduce this, but info about caches etc. would be helpful.