You need to use
tccutil to manage the privacy database -- this involves opening the Terminal and using the command line! If you know the bundle ID of the app you're trying to use, you can use this command:
tccutil reset ScreenCapture [com.WHATEVERBUNDLE.YOURAPPID]
Here are some examples for common applications:
tccutil reset ScreenCapture com.apple.Safari Safari
tccutil reset ScreenCapture org.mozilla.firefox Mozilla Firefox
tccutil reset ScreenCapture com.google.Chrome Google Chrome
tccutil reset ScreenCapture com.apple.QuickTimePlayerX QuickTime Player
If you're trying to use screencapture on the command line, your terminal application needs to be granted permission.
tccutil reset ScreenCapture com.apple.Terminal Terminal
tccutil reset ScreenCapture com.googlecode.iterm2 iTerm 2
If you don't know the app bundle ID, then you can just clear and reset the privacy settings for ScreenCapture for all applications. Note that this will remove all entries from the list of apps allowed to do Screen Recording, and you'll have to re-add them individually.
tccutil reset ScreenCapture
Once you've reset the privacy permissions, you must quit your application before the change will take effect. Then you can restart your app and try screen recording again, and the prompt should reappear.
Help, it's still not working!
Make sure that System Integrity Protection is enabled, otherwise these commands won't work correctly. To check, you can run
csrutil status and it should say
System Integrity Protection status: enabled.
You can also try creating a new user account with admin privileges and setting up the Screen Recording permissions in that account. That sometimes helps to put the TCC database back in a good state. This seems to be useful in some cases where the prompt window just isn't shown at all.