One cool idea (I saw it on Charles Stross' blog) is "diamond memory": use a diamond crystal, with two different isotopes of carbon for 1 and 0 bits. This also doesn't feel too unimaginable, in theory. According to Wolfram Alpha[1] this gives 1.75*10^23 bits (20 zettabytes) per CC.

[1] http://www.wolframalpha.com/input/?i=number%20of%20atoms%20i...