I'm having a problem with about a handful of Microsoft patches that are showing up as "green" in my patch management system, but when I try to deploy them to machines the consistently error out and in the details give a "not cached" as the reason for the failure. I have triggered these patches to re-update which again every indication shows that they have updated successfully but again give the "not cached" error weeks after I run the update cache operation. Aside from manually installing these patches from KB downloads (which works), what else can I try to do to push these patches?

I regularly see this error with the following patches among others:
MS11-100 2638420 2656353 Security Update for .NET Framework 1.1 SP1 (All Languages)
MS 931125 Update for Root Certificates (February 2012) (All Languages)
MS12-016 Security Update for Microsoft .NET Framework 2.0 SP2 on 2003 and XP x86 (KB2633880)

These were the easiest to find without trying a full patch deployment through my building to troubleshoot the issue. Thanks!