I used Mozy once upon a time, but had to abandon it because it never worked properly. Tech support was always very quick in their responses and very attentive, but they never solved the problem. I currently use Jungle Disk, which is a front end to Amazon's S3 service. It has a few different types of backup options and pricing (
https://www.jungledisk.com/personal/desktop/pricing/default.aspx), but you just pay for what you use. For your 40GB it would be $4.90 per month + $4 for the initial upload. Their drawbacks are as follows - slightly more complex than other offerings and no phone support.
Andrew.