Well I did not manage to uninstall MySQL and all data, so I had to do fresh installation of Windows Server 2012.
It took a lot of time to get everything working again but I am glad Plesk is working now with no duplicates users.
I am sure there must be an easier way than reinstalling Windows but at least now I know that Plesk is correctly installed with no-left overs from previous installations but I do believe, as feedback, this should be improved. There should be an option when uninstalling Plesk to completely remove Plesk or keep data for future installations. Maybe you can pass this on to development. I don't want to install Windows (with all server software afterwards) just to install Plesk again.