As someone who has looked through of thousands of domain names I can tell you that there are still plenty of decent names left. The trick, as I'm sure you've figured out by now, is finding them. If you took the approach I originally took, you've probably spent a few hours on AjaxWhois trying to find something that works for you and your site.

To help alleviate the headache, I created http://www.domainpigeon.com, which lists around 45K available domain names (and more are added daily). Most are not very good. That's just the nature of the game, but if you're willing to look, you'll find that there are many good names still available.

More than 500 have already been registered, so it can't be that bad :)

http://www.domainpigeon.com/domains/registered

Hope it helps.