2. Download Microsoft Visual C++ runtime libraries and install that.
3. Try installing it again.
Thanks for the suggestion, but this did not help:
RevoUninstaller only found the start Menu entry.
I get "A newer version of Microsoft Visual C++ 2010 Redistributable has been detected on the machine."
When trying to install both x86 and x64 versions of the Redistributable. Looks like I already have its SP1 installed.
I tried installing it on a machine, where no previous versions were ever installed, and it worked there - the client started. However, that is not the machine, where I'd like to have the client running 24/7 in full node mode.
Solved: After searching through the disk manually, I located and deleted c:\users\{user}\AppData\Roamin\Bitcoin nad it started to work after a fresh install.