I have used a number of different storage methods. I now have a CD-RW which is pretty good. I also have a Zip drive but it is a little cumbersome. Mine has to be plugged into the parallel port and I have to switch around a lot. I always worried that the newer, flimsy parallel ports would break. The other possibility is to have a second hard drive in your computer and store the backup on that drive.
The costs are pretty reasonable. CD-RW is most expensive at around $150 for the drive but the disks are really cheap. The Zip is about $100 for the drive but the disks are about $20. The second hard drive can be fairly inexpensive, say $75 to $100.
I just saw a web site to day that lets you save up to 50 MBs of data to their web server for free. You can use a search program for FreeCen and I think you can find it. My only quibble with that one is that you have to give them your email address, possible spam, and you have to let someone else have your data. Buty you should be ok unless their server goes down.
My newest machine has this "restore" disk system and I am a little worried about it. I can see where you might have a real bad situation if you have to go back to scratch.