But it isn't true that online backup requires giving the key to the backup provider.
There are two main security models: (1) All data is encrypted on the user's machine with a password known ONLY to the user that never leaves the user's machine, and the encrypted data is transmitted and written to backup exactly that way; on restores, the encrypted data is returned and then decrypted on the user's machine (Connected Online Backup from Iron Mountain and some ways of using JungleDisk work this way). Or (2) the data is transmitted securely, decrypted at the backup server, encrypted there with a key known to the backup service and saved; on restores, the data is decrypted at the backup server using the service's key, then returned securely to the user's machine (most other online backup services work this way).
The second model is, as you say, insecure--which is why it is a big competitive disadvantage.
The first model can be smart, of course, and employ the user's private encryption key which never leaves the client PC only for personal files, and use some other method on Windows system files, commercial application executables, and other files which are duplicated on millions of machines (identified on the client before encryption).
FWIW, Connected Online Backup does both incremental backups by changed file blocks and also does identification of files it already has seen and so doesn't need to send again (at all), while keeping the encryption key only on the client PC. You're right about the current price--Connected wants $995/yr for 50GB. Obviously that price level can't last much longer.