What if you forget one of your 25+ random characters passwords? Then how would you get your bitcoins back?
+1 extremely paranoid here too.
Besides "trust no one", I also like to stress:
NO compromise when it comes to securing your bitcoins.
Here's what I do:
I have a dedicated VirtualBox VM with Ubuntu which I only use to run the Bitcoin client. I use an encrypted wallet. I store this wallet in a small truecrypt container (inside the VM). Furthermore the VM itself (well, the .vdi disk image containing the actual data) is inside a truecrypt container on the host machine.
I also make sure to have frequent remote backups (in case my house burns down, my PC gets stolen, the FBI takes it, whatever). After every few transactions, I compress the truecrypt container (I mean the small one inside the VM which contains just the wallet) using 7-zip with AES-256 encryption, and send this .7z to three webmail addresses (one yahoo, one hotmail, one gmail).
All passwords (for the truecrypt volumes and the encrypted wallet and the 7-zip archive etc) are 25+ random characters.
The passwords are stored in KeePass (and in the truecrypt mount and backup scripts in the VM so I never have to fill them in manually, except when I'd need to restore a backup).
I will not get f*cked.
