Olá!
Você pode solicitar uma nova recovery key na Lost Account Interface do site
www.tibia.com (
https://secure.tibia.com/account/?subtopic=lostaccount). Uma nova RK custa 5 euros, o que dá mais ou menos uns R$ 15,00.
Para iniciar o processo de comprar uma nova, na Lost Account Interface entre com o nome de um de seus personagens e clique em

, então marque a opção "I need a new recovery key" na Lost Account Interface e clique em

. Na próxima página:
A primeira opção ("I would like to request a new recovery key. I am prepared to pay 5 EUR for this service") inicia o processo de compra, em seguida clique em

e irá para a tela de entrar as informações de pagamento.
Ao contrário das páginas anteriores, a página de compra se encontra traduzida para o Português. Cuidado para entrar com os seus dados coretos (da vida real) nessa página, eles não necessariamente precisam ser os mesmo da registração da conta (pois os dados entrados nessa página são os de quem está pagando). Vale lembrar que como a empresa que cuida dos pagamentos é alemã, o único modo viável para brasileiros pagarem diretamente é através de cartão de crédito internacional (o qual permite pagamento em outras moedas, que não o Real).
Se você não tiver cartão de crédito internacional, pode usar o serviço de
revenda do Boa Compra (lembre-se que por se tratar de uma revenda, o preço é um pouco maior do que comprando diretamente). Para maiores informações, acesse
http://www.boacompra.com/Default.php.
Após o pagamento ter sido efetuado, será enviado ao endereço (seu da vida real) registrado na conta uma carta (real e de papel) contendo a "confirmation key" (código de confirmação). No caso de um amigo meu, a carta levou menos de 1 semana para chegar. Esse código ainda não é a nova Recovery Key. Para obtê-la, volte na Lost Account Interface e vá de novo na opção "I need a new recovery key". Você estará novamente nessa tela:
Dessa vez marque a opção "I have already received the letter with the confirmation key for a new recovery key", que diz que você já recebeu a carta, e clique em

. Na próxima página:
Marque "Yes, I would like to get a new recovery key", digite a corfirmation key que veio na carta, e clique em

.
Então será exibida a sua nova Recovery Key. Essa Recovery Key
é exibida somente uma vez (então anote-a e dessa vez tome mais cuidado com ela), e cada confirmation key
funciona uma única vez (então tome bastante cuidado para não ter pago à toa). Tendo em mãos uma nova Recovery Key, agora você já pode usá-la, e a antiga não vale mais.
Abraços,
Magnus Hotblood