I have exactly the same problem - I am using Parallels Desktop for the last 10+ years (started from version 4) and since I have updated almost every year - I have together some 4 active licenses (plus 11 legacy ones!), including 2 PERMANENT licenses for Parallels Toolbox (from v12 and v13). It worked normally for many years, but after recent upgrade to Paralles Desktop 16 (from v. 15) the Toolbox stopped working after 3 months and my permanent license codes are not accepted?
I have read this thread and tried to download the version as suggeted by sergk but this cannot be installed on MacOS Catalina (system rejects this as "not safe and requireing updating by developer"). So apparently - as a result of me loyally upgrading the software I have lost access to Toolbox - which is entirely non-acceptable. Please offer me a reasonable solution to this or I would feel forced to stop any further purchases from you...
On a seperate note: I tried to get support from your facebook chat, but unfortunately the quality of this support is hopeless - your "consultants" (I guess - sitting in some call center in some remote country) seem not to understand the issue and even worse - are too lazy to read the correspondance before firing some "off the shelf" no-solution that is entirely irrelevant to the case - it is really a shame that you treat your long-term customers this way... (I can sand you a copy of these chat exchanges,, so you may think how to improve your support quality).
Regards