Today looking a WMT we spotted that we were linking to 1000's of 404 pages from our main pages that have been dropped.
I am curious about what percentage of the total URLs on the site those 1000s of non-existing URLs were?
I have a somewhat similar case where I'm seeing hundreds (although not thousands ) of 404 errors reported in WMT that are result of bad data in a very large DB and therefore are VERY difficult to completely get rid of. Basically, the only way to repair this would be to manually review and edit/delete several hundreds of bad records (which need to be identified first - a task in itself).
There is approx. 110,000 of legitimate URLs on the site now so, as a percentage, the number of those bad links is not too high. Still, the absolute number is high enough and looks really bad in WMT when compared to other sites.
I am also seeing a slow but steady degradation of ranks in Google and yes, I think you are correct in your observation that Mayday might have actually increased the rate of that degradation.
So, if a large number of INTERNAL bad links is known to have a negative effect on rankings, I'll have to bite the bullet, allocate a few days of my time and clean all that data. There is also a large amount (also in hundreds) of EXTERNAL bad links pointing to my site due to sloppy scrapers using my RSS but I cannot do anything about that and I sincerely hope that in this case Google would uphold their promise that other people's links cannot damage my site.
So, needless to say, I am very much interested in the outcome of this discussion and any relevant observations about the "quality score" and what factors may be used for its calculation that other people can post here.