I feel like domain names are difficult to find not because they are really being used up, but rather because there is no system governing them. What if we treated domains like trademarks, so if you don't use it, or stop using it, someone else who is using it can take the domain from you?
The thing is, this is also a problem for company names, and product names, and... well just about everything involving names. Almost everything is running out of names. We need to do a better job of recycling old names if any of this is going to be sustainable across any market.