When you republished the update did you duplicate the package and publish it as a new name? The Windows Update Agent caches the binary content so this could be what is being used again.
No. That makes sense as to why the issue was happening.
I found another work around, I expired the Adobe Flash Player 22.214.171.124 EXE (Upgrade) and published and approved the Adobe Flash Player 126.96.36.199 MSI (Upgrade) instead. This worked.
Thanks for the help, I now know how to properly fix the issue if it arises again in the future and I do not have an EXE/MSI package option/workaround.