To my mind, keeping copies of old, deleted files is an important part of a backup. Just to be clear, I wasn't using crashplan as a kind of media file store or anything - their restore experience was far too clunky for me to bother with that!
I'm more concerned about old files I've accidentally or deliberately deleted that I later turn out to need.
Anyway, my storage requirements are pretty low (probably 1tb) so I'm going to look into solutions like B2 with Arq (along with my existing Time Machine).