kazriko - You may realize that you can easily view "Page Source" from most browsers.  This makes it possible for anyone with the html and javascript savvy to simply examine the source code and verify that the Private Keys are never transmitted over the Internet.  Oe could also check the similarities between the page source of our Paper Vault pages and the open-source code available at bitaddress.org and in https://www.strongcoin.com/downloads/offlineTransaction.zip .  We have integrated these open-source tools into our own service in a way that makes them much more convenient use.  You can examine both our code and their code for yourself, if you like.

And yes, I would agree that if the user's computer is hacked or compromised (perhaps in a way which would allow a hacker to see everything the user does or types on his computer) then this would obviously introduce a security flaw.  I would like to point out that such a compromised computer would also be vulnerable in the event of dealing with traditional financial transactions as well.  We cannot guarantee the security of every computer in the world, but I would like to point out the the very security-concerned (maybe paranoid is too strong a word) could use a live-cd operating system for dealing with The Bank of Bitcoin, but that would apply to using any other online Bitcoin service as well.

As for the fee: we do not charge for creating a Paper Vault.  The 0.0001 BTC fee you referred to is for the creation of an additional Auxiliary Bitcoin Address for your Active Storage, not for a Paper Vault.  That fee (and all of our fees) is deducted from your Active Storage, never from Paper Vaults.  (It is inherently impossible to deduct fees from Paper Vaults, in fact.)