Hmm, glass jars maybe. You know, there's probably a lot of lost loot buried in old mason jars that old farmers planted and forgot about or lost track of. Baby food jars are airtight, long as the lid seal is still intact and handled right. I am guessing, though that you want something a little more durable than glass.

Polystyrene and closed cell foam can be pretty handy things for small, durable containers. Ever think of cutting a slit into a piece of closed cell foam, inserting a few matches, then sealing the end with glue or some such? I imagine the same could be done with styrofoam if you needed something a little more rigid.

I've also seen some pretty cool watertight containers made from rawhide coated with polyurethane.

Well, these may not be the best for long term storage, but they ain't bad.