conroy - 8:03 am on May 15, 2012 (gmt 0)
I've actually had one site with the message in WMT go up in traffic by about 60% even with this message, and even with them rejecting my reinclusion. I'm still about 50-60% down from panda though.
Google seems to be being rather thorough. If you can't remove most of the bad links they probably won't change anything.
It doesn't hurt to try reinclusion in my experience though.