If you go for the first solution that Mouser suggested, you could use the (portable) freeware version of RevoUninstaller, instead of the uninstaller from Windows itself. Any 3rd party uninstaller will do for the purpose of really cleaning your system of any residual files and/or registry entries. These are often much more resilient than you would expect.
Uninstaller software helped me out years ago when having lots of vague issues with Oracle clients on Windows systems. Then I found 3rd party unstalling software existed, tried the first one I encountered (Revo Uninstaller) and all my troubles simply disappeared. Since then, I never used the uninstall functionality from Windows itself.
Well, I should say that 3rd party uninstall software first uses the Windows uninstallation functionality and then takes an extra look in the registry and files on disk to see what was forgotten. And more often than not, that is much more than you would expect.
As you are experiencing a vague issue, it is likely best that you start from scratch, just as Mouser suggested. Except you should use proper cleanup tools, not only the build-in Windows functionality. Revo Unistaller is the one I have used for years (and never felt a need to change it for something else), but there are several more options available, in case you don't like Revo.
Regarding Mouser's second suggestion: Nowadays, I predominantly use portable applications wherever I can. Simply deleting a folder with the executables is enough to get rid of an application. There is software that give you a better experience when they are installed, such as browsers and mail clients. For work I have DBA tasks, scripting tasks, minor development tasks, documentation. But also maintenance of networks, websites, mail servers, cloud services and I would say that my (curated) collection of portable apps cover 85% of all those tasks.
What I mean with the above is that you shouldn't diss portable software off-hand. Those are more often than not much less complicated to deal with than installed software, if you 'grok' the concept. And by their nature, you can use them next to similar software already installed on your computer, without any risk of messing up those installed pieces of software. Unfortunately I have met a lot of people who don't get the concept, while more than savvy enough about computers/Windows/coding. Too different, I would guess.
Anyway, good luck hunting the bug(s).