I have an even better idea: manipulating growth rings of trees for message storage. If you want to store a 0, you cover the tree with a tarp for a year to stunt its growth. If you want to store a 1, you leave it uncovered. Bandwidth is 1bit/year.
You can make the tarp semi-translucent, so that it lets through just enough light to keep the tree alive, and produce a thin growth ring for that year.