Keys are 160 bits, if I recall correctly. Brute force would require a computer somewhere between the size of the solar system and the galaxy working for a very long time to find a lost key. By the time we can build a computer capable of finding a key, the issue will be moot.

Now you're just plain making stuff up... "between the size of the solar system and the galaxy":

From:

http://en.wikipedia.org/wiki/Key_sizeEffect of quantum computing attacks on key strength

The two best known quantum computing attacks are based on Shor's algorithm and Grover's algorithm. Of the two Shor's offers the greater risk to current security systems.

Derivatives of Shor's algorithm are widely conjectured to be effective against all mainstream public-key algorithms including RSA, Diffie-Hellman and elliptic curve cryptography. According to Professor Gilles Brassard, an expert in quantum computing: "The time needed to factor an RSA integer is the same order as the time needed to use that same integer as modulus for a single RSA encryption. In other words, it takes no more time to break RSA on a quantum computer (up to a multiplicative constant) than to use it legitimately on a classical computer." The general consensus is that these public key algorithms are insecure at any key size if sufficiently large quantum computers capable of running Shor's algorithm become available. The implication of this attack is that all data encrypted using current standards based security systems such as the ubiquitous SSL used to protect e-commerce and Internet banking and SSH used to protect access to sensitive computing systems is at risk. Encrypted data protected using public-key algorithms can be archived and may be broken at a later time.

Mainstream symmetric ciphers (such as AES or Twofish) and collision resistant hash functions (such as SHA) are widely conjectured to offer greater security against known quantum computing attacks. They are widely conjectured to be most vulnerable to Grover's algorithm. Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case.[8] Thus in the presence of large quantum computers an n-bit key can provide at most n/2 bits of security. Quantum brute force is easily defeated by doubling the key length, which has little extra computational cost in ordinary use. This implies that at least a 160-bit symmetric key is required to achieve 80-bit security rating against a quantum computer.

160-bit hash key, providing n/2 (80) bits of security. So, once available (and quantum computers are already becoming available), you'll have to double the key length just to get an actual 160 bits of security.

Compared to that, searching the entire volume of the earth for lost gold, say a cubic millimeter at a time would be trivial. And searching the entire ocean floor at this level of detail, through the top couple meters of crud, is totally possible right now, just not economically feasible.

From:

http://wiki.answers.com/Q/What_is_the_total_surface_area_of_EarthThe surface area of the Earth is 510,065,600 km2.

1 km is 1,000,000,000,000 mm2

So the surface area of the Earth is 510,065,600,000,000,000,000 mm2

I'll give you the benefit of the doubt in this discussion and say we're only searching water, which is roughly 70% of the Earth

So, that's 357,045,920,000,000,000,000 mm2 you have to search.

An 80-bit number (remember 160 bits only gives you 80 bits of security against a quantum computer) represents

2^80 = 1,208, 925,820,000,000,000,000,000

That's only 2 orders of magnitude harder.

Said another way. If searching the water covered portion of the Earth is "totally possible right now", then I would think something only 2400 times harder would be FAR from requiring a computer "between the size of the solar system and the galaxy".

Especially with the computing power of CPUs doubling every 6 months.