However, as of now no money has been lost, nor were any money of other users ever in any danger because of this, the service is operational as usual, we even redeemed the balances of users that did this. You think that we should have done something differently?
Of course no money has been lost. But the probability of mistakes, however low, is always there. If a big mistake happens, an apology won't cut it. Saying you can't afford to replace all of the lost bitcoins won't cut it. Those of us who used your service will properly feel stupid for having done so, and we'll have yet another security scandal to hit the media. Even MtGox has lost bitcoins.
If there's something you can do differently, one example might be to publish the "sendmany" transaction you plan to emit, a certain amount of time in advance, so people can verify for you that it's correct. By publishing the transaction, I mean in JSON format as you would pass it to the RPC (containing only bitcoin addresses and amounts), not a signed transaction that will go in the block chain.
Another thing you can do is tell us how you manage your private keys that receive the incoming funds. If you told us, "these keys are generated on an offline computer and the private keys never touch the internet", this paints a much better picture than the assumption that, for example, the security of the entire operation is hinged on nobody breaking into your machine which is online 24/7 and has its own public IP and has a half dozen ports open.
The ultimate solution would be a client-server anonymizer where the client always controls the funds until the server broadcasts a satisfactory mass transaction that all the clients agree is safe, and then the client software does all the signing. This would be bulletproof and would present virtually no risk of loss or theft to any of the clients.