Kirby/Allan- I didn't take GG's comments to mean that all or any of the site's missing from the big city searches were spammy, but rather the the methods used to fight spam may have been more severe than those in less competitive (spammy) areas. If you have to throw out more bathwater, naturally more babies will go with it. I think that's why sending in the examples of poor results is so important.
Trumble- If you have lost 70% of your Google referrals already, that may not be a problem since the "change" hasn't propagated to enough datacentres to have that sort of effect yet. Have you tried your queries here- http://18.104.22.168
GoogleGuy- Are we able to use the "What are some other things to look out for?" section from that page on our websites?