Infelizmente, não!
Conforme explicado no FAQ disponível no Tibia.com:
1. Before you connect your Tibia account to an authenticator app, you need to enter your valid recovery key. This is important because in case your mobile phone, tablet etc. breaks or gets lost, the recovery key is the only way to disconnect your Tibia account from the authenticator.
No fim, a recovery key é a única forma possível de remover o autenticador da sua conta. Não sei quanto tempo faz que você habilitou na sua conta, mas agora a CipSoft exige que você insira sua recovery key antes de habilitar o aplicativo. Com certeza isso serve para tentar mitigar um pouco esse problema (afinal, se você não tem a RK, não habilita, logo, não perde a conta).
Sei de pessoas que já entraram em contato com a CipSoft com o mesmo problema e a resposta é sempre categórica: eles não vão desabilitar isso sem a RK.
O endereço na sua conta estava preenchido corretamente? Estava atualizado?
É relativamente normal demorar para chegar a carta da recovery key, porém, caso o endereço no site esteja inválido, acho que sua conta está realmente perdida.