FWIW, I tried storing the private keys for a user in encrypted form, so they are only accessible when he enters the password. Of course this still doesn't help against a malicious admin, but someone who broke into the server would only have access to the currently logged in users bitcoins.
Unfortunately, the account handling turned out to work differently than I expected, so the next step would be to use the wallet encryption and get the client to handle multiple wallets.
But as I don't see a reasonable way (for me) of dealing with the legal implications of running such a site, I've mostly given up on it...
http://forum.bitcoin.org/index.php?topic=19451 [patch to remove private keys]
https://forum.bitcoin.org/index.php?topic=12403.0 [online wallet]
Edit: I'd be glad to team up with somebody who thinks he can take that responsibility..
My fear is what if my (german) government decides bitcoin is terrorism/childporn/drugdealers/whatever tomorrow, would I have a clean way of 'getting out'?