Edited: I just realize that you asked this question for a server. I believe that all of the services mentioned (including carbonite) are targeted for home/consumer usage, NOT professional/server use. I don't know which of these software specifically prevents installing on a server OS, but it does go against there terms of service. If you are trying to backup a work machine, you are generally going to be paying per GB.... sorry.
There are a number of backup solutions available that are similar to Carbonite ($55/year or $4.59/month for unlimited online backup)
Mozy is probably their most similar competitor. Also unlimited data, that does support USB hard drives (as long as they are marked as "fixed". See http://support.mozy.com/docs/en-user-home-win/faq/concepts/external_drives_faq.html). Price is $4.95/month
CrashPlan is a service that I personally like. It has more options, so it can be slightly more difficult to setup, but its certainly not hard. They also allow for simultaneous backup to a local disk for free. They offer unlimited online backup for $54/year or $4.50/month (if you pay for 3years it goes down to $3.47/month)
As minamhere mentioned: Backblaze also offers an unlimited backup for $5/month and appears to support external USB disks.