3rd party packages not applicable until Windows Update Maintenance is run

Were these packages previously published with a 512-bit certificate, and you've now deleted and republished using a 2048-bit certificate?

No these are all new packages that have only been published since the new 2048-bit certificate was in place.

It may be useful for us to get a look at your windowsupdate.log from a problematic machine. Can you provide a scrubbed version of this log so we can see exactly what is happening when these computers are checking in?

I've scrubbed the log for an affected machine from the time I approved the updates to today. It is about 3500 lines and I don't see an option to attach it within the post.

The last 100 or so lines may contain all the info we need. Otherwise pastebin.com may be a good option.

Here's the log including data from when the updates were approved.

http://pastebin.com/vYq8MhRp

So after making some changes and monitoring the installs for several days I believe I've resolved the issue. I deleted the existing updates from the WSUS server, duplicated the patches in patch manager, deleted the existing packages, renamed the duplicated packages, published the new duplicate packages, and approved them to the desired groups. Once I completed these steps the updates were properly detected as needed and started downloading to the clients.