Looking for a definitive answer to the safety of long-term storage, I emailed Gavin:

Barring any unusual attacks/bugs, should a paper wallet essentially last indefinitely, enduring hard/soft forks, etc? Or is it conceivable that the coins could become unusable in the normal course of Bitcoins growth?

His reply:

No.