First off, thanks to all of you for your many replies, the links and the help you provided!
Second, the permissions are all set correctly, only when the DB locks up then the permissions are somehow overwritten and changed to "no access". It is the same effect as someone would open the DB exclusivly on the hosts server. (Except for the creation of the .ldb file, what isn't created when the DB is opened exculsively). But the symptoms are the very same.
Third, the DB is not located in the original forum/admin/database folder but in a database folder outside of the forum directory that was created by the host for Access-database-use only.
@thekiwi, I don't get any error messages when the trying to access the forum while the DB is locked. The browser just tries to load for several minutes(!) and then comes up with "site is not available".
The only thing I can do while the DB is locked is to download it over the http control center my host provides. I can put the downloaded and unchanged DB on my local server and then it works without any problems.
I really would love to change the host, but as I said before, I'm hosting several sites there, and it would be really way too much work to change the host right now. Except for their crappy support and that DB lock-up problem everthing is working fine. It's a German host, called 1und1 (or Puretec, it's the same).
Funny enough, the problem didn't occur for the last 4 days now. That's a new record. 
But it will be back as it always was. 