Having same situation only much worse.
If Parallels is going to start counting activations then they need to provide a way to DEACTIVATE. This is just stupid crazy common sense.
I often reinstall OSX after destroying the system tinkering with application installers etc. As a developer I do package and test installs and quite often end up with crap everywhere that only reinstall can fix. Tie this in with 10.8 beta, reverting back to 10.7, back to 10.8 beta, to 10.7 then back to 10.8 release, then each 10.9 beta and then an official reinstall of 10.9 after release today. Not to mention upgrade from 2010 iMac (now sold) to mid-2011 iMac (now sold) to a late 2013 iMac.
I'm left with what Parallels says as:
Parallels 8 Desktop: activated on 9 machines
Parallels 9 Desktop: activated on 3 machines
Now some of this I can see as some confusion because I did buy a new iMacs one after the other.
Do I like to reinstall YES, Do I like to refresh my hardware YES. Lots of people do. Provide a way to Deactivate a machine like pretty nearly every other software activation system does.
I'll never buy another Parallels license or tell any of my family or fellow developers to do so until this oversight is fixed. Its VMware and Bootcamp for me now on. I also want my money back but I doubt that will ever happen.
8 hours now without Parallels, which I have paid for 2 licenses of each 8 and 9. My Wife and Myself. Why 2, because thats what Parallel's terms are.