I am pretty sure long before Bitcoin is mainstream there will be no "random key" wallets outside of niche applications used by professionals. Deterministic wallets are far easier to understand, and safer for the average user. Remember the QT client is the reference client and as such it is rather conservative at adopting enhancements. In time I am sure it will either be deterministic as well. With a deterministic wallet one simply needs to backup and/or print the deterministic seed once and the backup is valid forever.
Given enough time you probably will even see hardware deterministic wallets which are completely "user proof" in that the deterministic wallet comes with a preprinted "THIS IS YOUR WALLET RECOVERY DOCUMENT. PLACE IT IS A SAFE PLACE. TREAT IT LIKE CASH AND ENSURE IT IS NOT STOLEN. IF YOUR WALLET FAILS YOU FUNDS CAN NOT BE RECOVERED WITHOUT THIS DOCUMENT." User buys the wallet, puts the recovery doc in a safe, and if their wallet fails buy another one, scans the QR code on the recovery doc and is back up and running with no loss of funds.
Bitcoin isn't mainstream yet.
QT client is the reference node and increasingly not the best choice for casual users.
There has to be a complete, solid, well tested reference node to ensure the network operates as expected. It probably will always be "rougher" than clients designed for casual users. The need for full blockchain is probably going to drive casual users to more "friendly" (SPV) wallets anyways.