I would also like to here about this. Right now I am checking out the gscan2pdf project. It promises to run a scan and then run OCR and output a pdf. So, if it does what I think it might, it could be a key part to the equation.
I got really excited about backblaze when I heard about it, but alas, they do not have a linux client yet...
can use virtualbox+windows. not ideal, but one way.
crashplan looks like a good alternative to back blaze, with a nice linux client. Also, they have a free option to backup over the net to a friends computer (encrypting everything before it is sent).