I also would be weary of online storage.
I have my files in at least two places, with a third "time to time" backup. First is they are all on my work computers hard drive (a seperate drive from the OS, just for file storage). Next they get backed up to an external drive in an uncompressed format. Third I will burn DVDs of the most important files from time to time and put them in a safe place.
I can understand the appeal of compressed backups, but have two problems with them. One is that in most cases, you can't simply access the backup and use the files, you have to use software to decode the files and then access them. I like to be able to just open the drive, find my file, copy it wherever I want. Second is along the lines of what has already been said, when software changes you need to keep up, or the files become obsolete. Yes, this could happen with uncompressed files as well, but I stick with formats that for the foreseeable future won't be going away, such as TIF, PSD, TXT, PDF, and DOC. I would use a compressed system as a secondary backup, but not as my primary one.
Since I started using the above method, I have had just one of my storage drives fail on me, but didn't lose anything since I had the external backup. I also knew it was coming, the drive was starting to have intermittent problems before it outright failed. In case of the nothing else is working worse case scenario, I have a couple of good data recovery programs on hand. I've not had to use them yet...at least, not on my computers. ;)