Advice, if I may: Make more than 1 copy of that paper wallet.
Keep them in different buildings. A fire could give you a really bad day.
just an idea: perhaps a thin stainless steel sheet on which you could hand engrave (matbe even scratch with tungsten drill tip) or stamp the info might be in order. such sheet can be bought from hardware stores.
or if youre worried about metal detectors, maybe some clay tablet in a plastic drainpipe with endcaps that you bury somewhere.
perhaps in the far future some lucky people might find bitcoin stashes that used to belong to reclusive hermit miners that are worth the value of a nice small tropical island.
I guess you could use one of those dog-tag engravers at wal-mart. Might have to stretch the wallet over several of them though
Would people actually trust a service which engraved and mailed wallets? The trust would be about the same level as Casascius coins but the coins typically only hold 1BTC and are more curios than live wallets. It would be quite a risk. Maybe if there was a way to two-factor them (hmm, I think Casascius was talking about that for his coins so...)