They can dedupe without needing to decrypt. Tarsnap does this. The issue is with features like being able to reset your password, downloading and sharing files via the web interface, etc.
Yes, but Tarsnap (as far as I know) only dedupes your data i.e., if I upload the same file twice it will be stored once. This is easy, because two identical files encrypted by the same key (i.e., mine) are still identical.
Dropbox dedupes across users, if Alice and Bob both upload foo.txt with identical contents (but encrypted with their own keys) the encrypted result will not be identical even though the files are. Right now Dropbox does dedupe in this situation, which obviously required unencrypted access to both files.
