I was reading the following article from Search Engine Roundtable with a belly laugh. A couple of the examples posted in the comments are hilarious. Google is way off the results, and really should hold off on polishing their badge until they get it right. [seroundtable.com...]
I suspect backlinks are involved, which might take some time for Google to reindex.
It has taken over 5 weeks for me to see even a 50% reduction in the removed backlinks (cached and in WMT). Google is indeed very, very slow. I am suspicious as to how any recovery could have occurred on the update last week without manual action from Google. The spidering rate is so slow that removed backlinks are taking well over a month to get discovered.