Lost coins only make everyone else's coins worth slightly more. Think of it as a donation to everyone.
I wonder though, is there a point where the difficulty of generating a new coinbase is so high that it would make more sense to try to recover keys for lost coins or steal other people's coins instead? The difficulty of that is really high so for now it makes a lot more sense to generate but I just wonder what the real figures are.. would that ever become more productive? Maybe Satoshi can address this..
Computers have to get about 2^200 times faster before that starts to be a problem. Someone with lots of compute power could make more money by generating than by trying to steal.