Personally, I feel that no permanent storage exists.
HDD: They are mechanical and they can fail. But while they are still running, they can last quite long. Seagate ES2 series is designed to run 24x7 so in a NAS, its great. An additional layer of assurance with the cost included.
NAS: They are like HDDs and if you run them RAID 1, you get some assurance. But the problem comes when the RAID controller itself gets corrupted. Even if you have RAID51 (RAID 5 + RAID 1), all your data will be gone. And if you go for data recovery, they charge you by the number of HDDs you have in the array.
CD/DVD: It is not permanent. They have a life span. I have CDs and DVDs dying on me just after 5 years. And do not scrim on quality if you choose to go this route. Do not go for OEM or cheap brands. There are Kodak-branded ones with an advertised life span of min 50 or 100 years.
Online: The companies might just close down one day, bringing your data along with them.
Flash Media: I feel that these are the best for permanent data storage but they are expensive. And they are also prone to corruption. I have a flash card that got corrupted when I insert it into a card reader that is a bit faulty (I didn't know beforehand).
I feel that the best way is to get a NAS, and then buy a data protection plan along with it. There are a few data recovery houses in singapore that sells the data assurance plans. You pay something like S$200+ for 3 years or so. And during that period, should your HDD or NAS dies, you can have unlimited data recovery. The good thing about them is that your data can be 99% recovered most of the time. If you approach them when you have a prob, the costs can be very high... around S$1200+ for a 80GB HDD.
Otherwise, get multiple storages like some of the bros does it. The pain is not worth it when disaster strikes. Personally, I have the unfortunate experience of visiting the data recovery centres for 3 times.