I have a lots of ideas to help this...
As for example, I´m gonna build some kind of online Wallet storage based on Eucalyptus and Ubuntu (open source Cloud Computing).
1- Each user will have its own private Bitcoin / wallet.dat "instance";
2- The wallet.dat will be stored withing the "Walrus" (Eucalyptus persistent storage);
3- The Ajax interface can have a "backup wallet button", wich stores your wallet within GmailFS, DropBox, or download it directly to your compúter. Also, after every transaction, the system can automatically backup your wallet in any place you want (pre-configured).
4- The users will be able to download the wallet.dat to its own computer and open it with Bitcoin software;
5- The users of this system, will not have access to the "Cloud Frontend", the bitcoin/wallet will be accessed through a Web Ajax Interface only;
6- The persistent storage of users wallet (Walrus) will be encrypted with the user password, so, the Eucalyptus administrator (ME and my team) will NOT have access to ANY wallet.dat, never.
Playing the role of the malignant admin again

3. Sounds like the perfect way for a rogue admin to backup a wrong/empty wallet over-writing the user's backup. Or it might not even need to be malicious, a bug could cause the backup wallet to be wiped. Furthermore, sending it to yet another external system seems to be increasing the vectors by which the wallet could be stolen/attacked.
6. Doesn't stop a rogue admin from capturing the user's passwords in the first place to use for decryption

3. I have a rule in my IT life: never overwrite anything. This can be so simple as:
#! /bin/sh
BKPTIME=`date +%m:%M:%S-%d-%h-%y`
tar czf ~/wallet-$BKPTIME.tar ~/.bitcoin/wallet.dat
cp ~/wallet-$BKPTIME.tar ~/Dropbox/
6. Right and wrong at same time... All passwords are encrypted and saved into /etc/shadow only (or even a LDAP backend), so, how long will take to decrypt a strong password?! +100 years?!
6.1. Don't you trust in your system, when you type your password to login into a SSH session?! This can have the same level of security than SSH has.
Also, it is perfectly possible to encrypt your Dropbox/GmailFS/Ubuntu One/Whater cloud folder too...
What do you think Xephan?!
I know that deep inside, trust between two parts must exist but, the provider can have a high level of security and strong backup procedures that a single user never dream about. So, where you prefer to host your wallet.dat?! Within a strong cloud that you can trust for sure or within your freak Windows?!
Sorry, I don't know if you are using Windows...
I can garantee that a system created by me, using well know open source tools and pretty well documented, is far, far away more secure than any Windows out there.
BTW, there is no secure Windows. So, every single person wich hosts their Bitcoins in Windows, have the same level, or worst, of security than MyBitcoin... Windows is a joke... Like the todays online wallet providers.
Best,
Thiago