Also, I understand that the Recovery Code is supposedly the last resort...but the fact is I just can't locate it. What are my options now? Can I really no longer ever use Teamviewer? Do I have to create a new account? What do I do here?
I had the same issue and contacted Teamviewer support. The one individual I dealt with was virtually useless beyond telling me that I can't get into my account w/o a security code from an authenticator app or my recovery code. They did not provide any other options on how to gain access to my account.
I, like you, am diligent about saving recovery codes but was unable to locate it anywhere.
In the end, and after numerous emails back and forth to Teamviewer, I realized that my old phone had the authenticator app and I was able to get past 2FA.
In your case, if you don't have access to the old phone then you are not going to be able to get into the account. To the best of my knowledge, you will have to create a new account.
