Well, after successfully installing the Qt to another Windows 8.1 machine I copied the "C:\Qt" and "C:\Users<USER>\AppData\Local\Roacming\QtProject " folders to the machine where it didn't work. But still qmake did not work.
So, I knew that the only thing different on those two machines was the "COMODO Internet Security". After uninstalling that junk (disabling didn't seem to help), qmake is now working properly and I can actually use Qt Creator.
This was another reminder why I switched to linux on my main comp years ago. Hopefully this message will help anyone in the future: turn off your anti-virus or if that doesn't help, uninstall it. I wish the Comodo could have at least informed me that it had blocked the software...