Forgive me for being presumptuous, but I would venture to guess that the majority of the problem is created by a few widely used packages.

If this is the case, I'd think that fixing a few widely used packages might reduce the problem a lot; thereby reducing the time constraints such that you'd be able to clean up most of the package collection over a more extended period of time.

-Scott

Update: For a more specific suggestion, I'd call your attention to this:

"some of the problem packages it turns out that many of the included packages are included for a function that only gets used in a few specifc places

Remove those "seldomly used" sections, and create yet another package for those.