Coins become lost when the private keys to them aren't stored anywhere, and nobody is holding them. So though the coins never really disappear, they can't be moved anywhere, because no one has the private keys required to move them.
Can't the private keys be cracked the same way they are discovering new coins?