Another Reported XBox 360 vs. Windows Live ID issue
I found another report of Gamertag issues due to trouble with Windows Live IDs, this one in an article titled “I Lost My Gamertag and Microsoft can’t find it“. The story there is a little convoluted and not exactly the same problem, but I’m pretty sure our two problems are related and if Microsoft could fix one of them, it could fix both of them. (And all the others posted I’ve already written about).
Again, I don’t know if it will help, but if you see this and have the same problem, post about it on this page (at getsatisfaction.com)