I spent a loooong time looking at companies and there are lot of cowboys. Lots of deals that seem really good, lots of companies that are really just resellers, not a lot of transparency going on.
I went with CrashPlan+ Unlimited in the end. I have it running nightly on my backup server and I've got the best part of 1TB of data up there now. Everything's compressed and encrypted. Restoring files is really straight forward and works a treat. Got to say I really think the whole service is great and amazing value for money