JungleDisk won't do it directly with rsync, but their software does provide the same basic functionality of backing up only changed portions of files. If you've looked at it in the past this used to be called JungleDisk Plus and was an added-cost service beyond the base software license; they now just charge a slightly higher cost per month with no upfront cost. They have a $2/month plan that's backup-only and targeted at basic users (Grandma) and a $3/month plan that includes network mapped drives and other features.
Since you're probably in Europe based on your pricing, it's worth noting that JungleDisk offers 3 options for file storage (all include the first 5GB "free") - Amazon S3 in the US for $0.15/GB/month, Amazon S3 Europe for $0.18/GB/month and Rackspace US for $0.15/GB/Month. Both Amazon options charge for bandwidth, Rackspace does not. If you're very price sensitive, Rackspace US would be the way to go, otherwise Amazon Europe may be faster for you.
With Rackspace storage, you'd be paying around $9.75/month total; with Amazon EU you'd be paying $12-13/month depending on how much data you were moving each week and your initial upload would cost around $5. Subtract around $1.50 for Amazon US.
JungleDisk also runs on Windows/Linux/Mac.