Just curious as to why you are specifically looking to storage online ?
One problem is with companies being taken over and something that at one time costs X pounds a year suddenly costing multiple times X pounds. Their attitude may be 'take it or leave it'.
It rather depends how many GB of data you have, too, because there are some online services which have no fees (eg the Microsoft owned 'Live.co.uk' offers 5GB + 5GB of storage, free (sorry, think half is for plain documents and half for MP3s/multimedia files)... and others like Carbonite which have annual fees. There have been 2 or 3 threads recently and plenty of other options.
Suggest you use 'advanced search' for 'online storage' for the last 6 months on topic 'geeky stuff'.
Of course, best to have an external drive too, and these days, 35-45 quid should get you up to 500 GB, while 50-70 quid should get double that.
I know how you feel. I have gigabytes of photos collected over the years and once honestly thought I'd wiped the lot after thinking I'd made a backup when in fact I hadn't then wiping my hard disk to reinstall Windows. Honestly for that day I was inconsolable! Luckily i managed to piece everything back together through various sources.
Like you I've looked into online storage but the main problem is upload speeds of our Internet connections. Simply they aren't really quick enough for that first upload. You'd have to leave your PC on for literally days if you have as many photos as I do.
So instead what I've done is bought a couple of external 500GB hard disks. I copy to both and leave one with a trusted neighbour. Every so often I ask for it back, refresh it then pop it in again. Low tech but if my house goes up in flames then at least my photos & videos are safe. That's about the only thing insurance can't replace. Memories.
I do exactly what niceguy2 does. We were going to get the Tech Guys one, it was £35 a year for unlimited storage but dsg have now changed to Know it all or something like that changing it to £50 a year and only giving something like 50gb of storage. We have 2 external hard drives, one we keep in the car and the other my mum and dad have. Everything has a usb port (apple excluded) so it won't matter if you change your computer regularly you'll still be able to connect it.