A mi me pasó algo parecido, cuento la historia, quiza te ayude o te dé ideas para solucionar tu problema, pero no prometo nada:
Yo tenía una cuenta, "DarkNoid_TE_MATO" asi se llamaba mi cuenta. El caso es que de repente un dia no podia entrar, lo intente una y otra vez pero nada, yo pense igual que Tony_greenday, lo primero que hice fué ir llendo a casa de mis amigos que podian conocer mi contra, por supuesto no dije nada de que me habian robado la cuenta, lo que hice fue lo siguiente:
Uno por uno fui visitando a mis amigos, llegaba a su casa con la escusa de echar unas partidas al pro, cuando llevabamos un rato jugando le decia cualquier cosa para que saliera de la habitacion en la que estabamos, (yo siempre utilizaba la tipica escusa de "creo que te estan llamando") y cuando salia de la habitacion me metia a ver si habia puesto mi ID en recordatorio, a la 4 vez encontré al ladron. Y mirar vosotros que fue justo del que menos sospechaba, alguien con el que hasta habia ido a parbulitos juntos. Me dijo cual era la contraseña y asi pude cambiarla.
Eso de vincular tarjetas de credito son chorradas amigo, si quieres comprarte algo mejor utilizar tarjetas de 20€ que venden en cualquier tienda de juegos.
Y nunca pongas una contraseña que no contenga numeros, letras y mayusculas, asi sera mucho mas dificil que te roben la cuenta.
Espero que puedas recuperar tu cuenta y que ese desgraciao arda en el p*** infierno. xD
Salu2