Sabem o endereço de registro, na página da sua conta? Antes de tudo, tenham certeza que ele está totalmente correto, pois é pra lá que eles vão mandar a sua RK nova. Se estiver errado, troquem para o certo, isso demora 30 dias. Para ser confirmado.
Depois disso, vão no Lost Account Interface do Tibia.com, ponha o nome do seu personagem, e marque a opção "I need a new recovery key", e logo então em "Submit". Depois, marque "I would like to request a new recovery key. I am prepared to pay 5 EUR for this service.". O serviço requer cartão de crédito internacional, e custa 5 euros, em torno de 18 reais com todas as taxas de câmbio. Se você não tiver cartão, não se preocupe, você pode fazer a solicitação pelo BoaCompra, e dá pra pagar direto em reais, por boleto ou cartão não internacional, transferência bancária, whatever.
Depois de pagar, em até um mês, eles vão te mandar uma carta, pro endereço registrado, com um código, pra poder resgatar sua nova RK no site oficial, com todas as instruções lá, no papel.

Boa sorte =)