It's a fundamentally tricky problem:
Proof-of-work/low-difficulty-brute-force is the obvious approach; but it's hard to calibrate: You don't know what advances in computing and cryptoanalysis may or may not be made (we aren't even talking sci-fi stuff here: In, say, 1995, 3dfx Interactive had been in business for about a year, rainbow tables wouldn't exist for another 8 years, Crack was still pure CPU and wouldn't support clustering until v.4. It's only 20 years on, and the situation has...changed a bit.)
You can't control how the adversary will traverse the keyspace: on average you find the key about halfway through; but if you get really lucky it could be your first try, if you get really unlucky it could be your last, or anywhere in between. Even if you perfectly predict the future and calibrate the size of the keyspace properly, you still have an uncontrollable probabilistic element.
Using some sort of tamper-resistant keystore with an RTC seems like an attractive option; but that has a fundamental weakness (in addition to any practical attacks that a given device may suffer from): In common use, tamper-resistant storage hardware has broad freedom to just blank the storage and thus frustrate an attacker. This is what they are supposed to do. Nobody cares about the lost data because they are either just authentication secrets(a shared secret seed on RSA fobs, a private key embedded or generated during manufacture for SIMs, CACs, chip-and-pin cards, and similar) or an offsite copy of something that is backed up in the locked datacenter back at the office(as with most Ironkey deployment scenarios). Authentication secrets are meaningless, IT can just issue you a new one and invalidate the old one at any time, no problem. Offsite files aren't meaningless; but the field copy is usually presumed to just be a convenience thing, and its destruction much preferable to its compromise.
Things are more difficult in the 'time capsule crypto' scenario: If there is an authentication entity that can just issue new credentials, they'll just get the subpoena and the whole arrangement is for nothing. If there is not, you can't just blank the storage at the first sign of trouble; because what is being stored is either the data you wish to store and protect, or irreplaceable keys to that data. Unfortunately, this takes the greatest weapon a tamper-resistant system posesses right off the table. If the system is free to nuke the keys, the attacker has to sneak past or disable all the defenses and tripwires the designer adds to the system. If the attacker knows that the system can't nuke the keys, because they are valuable, he can do more or less anything he wishes, so long as he doesn't directly destroy the memory himself. Under such relaxed conditions, very few systems could resist for long, definitely not as long as you would want.
The most theoretically elegant (but wildly impractical) solution I've seen proposed is to locate a reflector X/2 light years away from earth and optically transmit the key at it. Highest-latency delay-line-memory in the galaxy, and, unless you snagged a copy of the key as it was transmitted, you'll just have to wait X years for the reflection to come back to you.
A much less satisfying; but probably more practical, approach would be to use one of the secret sharing schemes that allows you to chop the key into N parts and construct them such that reconstructing the key requires at least M of them, with M somewhere between 1 and N, inclusive. This provides no elegant theoretical solution; but it allows you to choose your own balance of risk of permanent loss vs. risk of premature disclosure, and makes it about as easy as it can be to distribute the keys across multiple institutions, jurisdictions, storage media, etc. so that any given adversary will have a hell of a time subpoenaing, hacking, stealing, coercing, etc. enough of the parts to reconstruct the key.
You don't even need to tell the piece-holders who the others are, how many of them there are, or anything else. Just affix their chunk of data to a suitably durable storage medium with instructions to 'send to location X at time Y'. This isn't elegant; fundamentally you can roll the piece-holders one by one just as easily as you could a single keyholder; but in practice, especially if you don't know who all of them are, navigating a maze of different jurisdictions, some hostile or indifferent to your authority, is going to be much more of a challenge than just accessing a single one.