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"?
Normally, a transaction has 1+ inputs and 1+ outputs. Each block has a special transaction in it that has no inputs, which is used to reward the miner. Where the input would normally be is a freeform field named "coinbase". The term is also commonly (but incorrectly) used to mean the generation transaction itself. (My bad.)
Once upon a time, a guy mined two blocks using the exact same address for the reward. Both of those generation transactions were identical, so they had the same hash. In bitcoin, the hash is a, ahem, "unique" identifier, so spending one of them spends both of them. Thus, 50 coins "destroyed".
This won't happen again because blocks are now required to have their height in the coinbase field, which makes them unique even if they are otherwise identical.
And the network only checks that the generation transaction's value is less than or equal to the subsidy + the fees. Nothing stops you from making a block that claims less than the full reward, but doing so is silly, and nowadays, expensive. A few blocks in the past, however, claimed less reward than they could have, so the worldwide total will be slightly less than it could have been.
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.
Any 256-bit string is a private key. Multiply (in EC math) G by that private key, and you have a public key. Hash that public key in a particular way and encode it and you have an address. Neither the multiplication nor the hashing are reversible. You can pick a random number, hash it and see what the address would have been, even though you don't have a private key that would work for it. Or, you can skip right to the end and make an address without knowing what the public key should have been, much less the private key.
The address hash is 160 bits. We do know that for every input, there is one output, but we don't know that for every possible 160-bit number there is necessarily an input that creates it. The address in my hash, for example, has a pubkey that can be hashed to create it. But we don't know if there is any pubkey that hashes down to the bitcoin eater address.
I'm not sure if EC multiplication has the same property or not. I *think* that for every valid public key, we know that some private key matches it even if we don't know what that private key is. A proper cryptographer could answer that for sure.
