I accidentally pressed get new recovery key and this made my old key failed. I pressed the fallback button and it told me fallback failed. How can I get a new recovery key in this situation?
you only get a new one in case Fallback was a success.
What is the exact Story (ordered) of what happened?
Fallback happens in the end when you did reset your password but you did not mention this.
Getting a new key makes the old one invalid but you can sue this one in case you did reset your password.
What is in the client log when Fallback fails?