They are lost for good.  Think of it like someone losing their wallet in the ocean.  It seems like it would be a problem but it's really not that significant.  People lose their gold jewelry all the time but it doesn't make much of a difference to the value of gold.

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..