Well, if the gamertag is linked, and you recover on a 360, all you need is the email they used and the password.
If it's not linked, and your using a Xbox, you need the name of the credit card holder, the WHOLE credit card, expiration date, city, state, and zip code.
If it's not linked, and your using a Xbox 360
, you need the credit card holder, the LAST 4 DIGITS of the credit card, city, state, and zip code.
If you want to recover an easier way for the Xbox, buy a memory card, put it on there, and sell the memory card to the person who wants it.
For the 360, I've never seen a memory card, but would you send a $100 HDD? I don't know.
Does that answer your question?