So, is it theoretically possible to reconstruct those lost wallets and to get ahold of coins?
Not that we know of. Even if all the network's computing power could be devoted to the task, it would take bazillion years to find the private key of one address by trial and error.
In theory, there may exist some magic algorithm that allows one to do that in a viable amount of time. That would not only break bitcoin but also a lot of e-commerce and e-banking systems. But no one has published such an algorithm, and apparently no one knows how to even start looking for it.
[ ... ]
The bitcoin protocol gives about 3600 BTC (about 1.2 million USD) every day to the miners, no matter what. The fraction that one miner gets from that bonanza is the same as the fraction of the total hash power than he controls. Therefore, each miner who is making profit will want to have as much hashing power as he can, to maximize his profits. That is the reason for the mining race.
Well, I'm stuck here:
http://bitcoin.stackexchange.com/questions/22/is-it-possible-to-brute-force-bitcoin-address-creation-in-order-to-steal-moneyThe math posted there is ok for me but I'm not familiar with crypto so those parts are over my head for now, Anyway, as one can see, there is no consensus among experts. Interesting enough, it seems that one post there clearly reads "It is possible to brute force some Bitcoin addresses, because some people generate their private keys in an insecure manner." and further the author even gives some practical cases! Please have a look at it. Most answers says it's totally impractical if not entirely impossible while few seems to point that it is doable, in principle, but it would require a lot of hashing power (my concern exactly: where is all the missing hashing power going?!) and instead of attempting an attack it would be more convenient to mine directly (yeah, but now the reward is halved so things significantly changed). So... what shall I get out of it?
As about the variance in hashing power, please see my above post (and graph). Maybe I was not clear enough as we may have a slight language barrier on my side.