Hi ivahost,
After applying the workaround mentioned in above replies(set start up and shutdown manually), my mic has been working for two weeks. But today I entered a state similar to yours, i.e., I have Parallel Desktop listed and checked in MacOS's mic security setting, but I'm still getting the pop up saying parallel cannot access the mic. I have struggled for a while and finally make the mic work again. Not sure which of the following really fixed the problem. You may try if any of below helps for your case.
1. Set Parallel to be start and shutdown manually
2. Exit Full Screen Mode (my original problem started with strange graphics in full screen mode and cannot exit full screen mode)
3. Select "Shutdown" from parallel desktop (instead of selecting shutdown from guest Windows)
4. Exit Parallel Desktop completely (there is no small dot below the parallel desktop icon in dock). In some of the attempts, sometimes Parallel refused to be completely closed.
5. Reboot MacOS
5. Set the Mic in Parallel again.