The only time this has ever happened to me was on VBulletin (bear with me, this is still relevant). It was when I was hosting with 1&1 and they had a particular combination of PHP and MySQL that was causing a problem writing some stuff to the database. The first myself and many other forum owners on 1&1 noticed was that threads would spontaneously vanish, always after someone had added a reply.
The evidence for this, and this is where I suggest you look, was in the raw database. The post and thread records were still there but the ID numbers were corrupt or blank. So, my suggestion would be to use PHPMyAdmin or similar and look for orphaned content. However it is vastly easier if someone remembers an actual thread or post that vanished, so you can narrow it down.
Other than that, I can only see this being a permissions problem (which you have ruled out) or a rogue member or hacker with the access required to delete content either from within the forum, or through your database. It won't do any harm to change all passwords and just run a check on what accounts have this sort of access and change passwords on those too.
Hope this is some help. It can be a nightmare sorting out things like this.
