Here goes 
1. If the "golden image" is updated with Windows patches, then should the provisioning machine always be updated with the same WIndows patches (at the same time the golden image is patched)?
Preferably yes, you would also update the package machine after the GI has been changed. Our experience is that if you do not do that for a couple of months it wont stop your environment from working. If you however update the Appvolumes Agent or any other big thing (like a new office version) then yes, do recreate the package machine.
2. That's great for any new AppStacks created after patches are applied to the provisioning machine - they'll have the same patches as the updated provisioning machine and patched golden image. But what about any existing AppStacks created without those patches. Do they all have to be individually updated with the patches that were applied to the golden image?
Never ever install patches into an appstack. This way your machines will get all funky and stuff.. Appvolumes works like this GI --> Appstack --> last assigned appstack --> Writable. So an appstack always takes precedence to the GI. This would mean that your patches would come out of the appstack, not out of your GI and you do want your patches coming from you GI, always. Worst case scenario you would nee to recreate the appstack after patches have been released on the GI on a newly created package machine. My experience is that there is no need to do this every month (see my first answer). Just keep an eye on your environment. If you see some strange thing happening with a specific appstack and patch just recreate the appstack, way easier,
3. This was also the first time I remember seeing that applications installed on the golden image should also be installed on the provisioning machine. Seems like that would bloat the size of all AppStacks. I thought the provisioning machine should be as clean as possible - seems that this instruction is in conflict with that.
No it wont. Your packaging machines needs to be as close to your GI as possible that does not mean that all applictions will be installed in an Appstack. Lets say you have Chrome installed in your GI. If you were to package FireFox in an appstack, Chrome would not be in that appstack as no changes to Chrome were made during installation of Firefox in the appstack. If, for whatever reason, Chrome updated itself during packaging, then yes, it would also be in the appstack. So make sure to disable all auto update services in your packaging machine.
4. If applications should be installed on the provisioning machine too, should we just be making a clone of the golden image after patches and use that for the provisioning machine?
Yes, this is even a best practice.... I would suggest renaming the machine and readding it into the domain.