Perhaps there could be some way for clients to periodically verify ownership of the transactions associated with their key, if there's no verification for a significant period (several years?) the funds get released back into the potential mining pool. I don't know how difficult this would be to code.

It's going to become a real issue at some point in the future, where minting new coins is near impractical. The rate of permanent loss will exceed generation.