I conducted some random tests and did notice some of these free web directories not coming up in Google. Later in the day, Terry Van Horne began running larger tests on 500+ web directories and noticed as much as 16% or more are no longer showing up in Google. Based on his initial numbers, there are over a 100 web directories that are not indexed by Google.
I do not know if these directories were ever listed in Google or removed recently due to one of the recent Google updates; i.e. Penguin, Panda refresh, blog link network elimination and unnatural link warnings.
I did ask Google for a comment on this specific case and Google declined.
Have you noticed a recent massive delisting of web directories from Google’s index?
Postscript: SEOmoz did their own analysis and claims 20% were removed, 20% of the web directories they looked at are no longer showing up in Google. They looked at 2,678 directories and checked to see how many of those are in Google.