Cannot activate after clean installation (license issue)

I decided to do a little spring cleaning and clean (re)install Windows 8.1 Pro to my Bootcamp partition. I downloaded the Windows 8 Pro files by choosing create install media (ESD-USB). I actually had trouble getting this far as my Windows-route was Windows 8 Release Preview license -> Windows 8 Pro Upgrade license (bought from Microsoft) -> Windows 8.1 Pro Update. Anyway, I now thought that I could just erase the Bootcamp partition, create a new one and clean install Windows 8 Pro with the ESD-USB media. Unfortunately this is where I realized that I had made a mistake. Firstly, my iMac didn't support Bootcamp installation with USB media. I then chose to go the virtual machine route (which is handier anyway as I hated the constant booting when switch from OS X to Windows) and downloaded Parallels. The Parallels installer accepted my Windows 8 Pro license and installed Windows 8 Pro. After some tweaking, Windows accepted the license key as well but, alas, informed me that the key was being used by another computer. I did a little reading and apparently I should have deauthorized Windows before erasing it. I also read that even though I'm using the same computer and the same hard drive, Bootcamp (partition) and Parallels (virtual machine) might be interpreted as being separate as far as licensing is concerned.

Could someone help find a way out of this mess? What I have is Windows 8 Pro Upgrade key and a Windows 8 Pro ESD-USB media. I want to install Windows 8 Pro (and of course then update to Windows 8.1 Pro) on Parallels but cannot activate it after installation because of the license being used on another computer. Is my only option calling Microsoft for key reactivation or are there any tricks I could do? I've read something about the use of generic Windows keys...

Please help!