You may blame Microsoft for this. Apparently, their Windows OS group believes that they have the responsibility to make sure that you know that they have some other software that Microsoft prefers you use to open a particular file type.
This problem is not confined to .pdf but you will also find it for .jpg, .tif, and .png file types normally associated with Photoshop. Nor is it limited to Adobe products. You will find the same interference by Microsoft for music file types such as .mp3, .mp4, and .wav if you are trying to use iTunes from Apple.
Typically this issue is seen after any and all Microsoft OS updates such as the typical “patch Tuesday” updates (now occurring anytime). The above dialog appears usually after the first time you try to access a particular file type after the OS update the Always use this app to open option, that normally stops the obnoxious behaviour until the next OS upgrade/update.
Sorry that we can't be of further assistance with this. Complain vociferously to Microsoft on their forums. Maybe they might listen!
Any update on this? I understand the "Patch Tuesday" and the fact that you said other files/programs experience the same issue, however, we have only one user (our CEO) that is experiencing this issue. She is only getting prompted when opening Adobe docs too, specifically PDF.