Bitcoins are very abstract. The definition of "destroyed" gets fuzzy here.
Blocks claiming less than the full possible reward most closely fit, in my opinion, the concept of destroyed. These coins can only be recovered by a change in the protocol.* Also in this category is the permanently unspendable coins from one or the other of the two blocks that had identical coinbase transactions.
What is "coinbase"? How do you get a block that has "less than the full possible reward"?
Coins sent to keyless addresses are the second best fit. No one has ever known a privkey that could redeem those coins, and so we have no reason to believe that such a key exists.
Coins sent to keys that were generated but then lost is the weakest fit. We know that a key to that address has existed in the past, and so there is every reason to believe that the key could be found again. Thermodynamics blocks us from doing so, but math itself doesn't bar our way.
* Such a change may not be completely crazy, but is still really unlikely. It wouldn't hurt much to allow miners to claim some fraction of the coins lost through this method in the past. Of course, it wouldn't help much either...
How do you get a valid address with a key that "doesn't exist"? How is an address where nobody ever had the key any different than an address where somebody had the key but has really absolutely permanently lost it. Let's say they generated it in volatile memory, wrote it on paper, shut down the computer and then burned the paper... how is that any different to a valid address where nobody ever really had the key?
And on that note how do you make a valid address but without ever getting the private key? Aren't valid addresses generated from private keys? I mean when I import a private key it knows the address without me telling it just from the private key.