I don't use the service so can't comment.
But I would only use any remote backup system if I had some trust for the company providing the service. I don't really trust Virgin media, so would not use their service.
External hard drives: just goto somewhere like amazon.co.uk or ebuyer.com and find the largest capacity ones you can afford (you will use all that space eventually, I guarantee it). Maxtor, LaCie, Western Digital, Hitachi, Seagate, are all good brands.
Then either use a free program called CloneZilla (which you put onto a CD), which will allow you to make a perfect copy of your internal drive, or you use a program like SyncBack (free) to copy certain files and folders that you want backed up, systematically. Do the former once a week or every few weeks, and the latter once a day or every few days (since it takes so little time). Neglecting backups is never good!
Backup of (legally) downloaded music: yes, that will constitute copyright theft. However, check the license agreement you signed from whatever company you purchased these songs from to see if this use case is allowed. For example, Apple provides a legal music purchasing system with iTunes. On their Macs is a piece of software called Time Machine, which does a good job of backups; this also backs up all your music, so it must be from by Apple.