I've been on this site for the past 2 days trying to figure out what the hell has happened and the only logical conclusion I have come up with is this:
If you had an Xbox, regardless of version number, that was un-modded when you got XBL, and proceeded to mod it, then you're busted. If you modded your xbox before you got XBL, then you're in the clear. I believe MS registered your EEPROM and HDD serials when you got on XBL. Then, if ONE of them changed and one stayed the same, then you got banned because they'd know something was up. Furthermore, once you were banned, your EEPROM and HDD serials were banned that if you tried to use EITHER of them, then the that combination was also banned. Once a serial is banned, you cannot use it again. Period
An example for those who are lost:
Johnny buys an xbox. Johnny gets XBL. Johnny gets on XBL with his new xbox. Johnny decides, "I want to make backups of my games so they don't get ruined and only use my original retail copies for XBL." So Johnny gets his xbox modded with a huge hard drive. Unfortunately, Johnny's new harddrive serial doesn't match the stock harddrive serial that he used to get on XBL originally, yet his EEPROM serial is the same, so he's banned even tho he turned his modchip off.
Across town, Sally buys an xbox too, but she knows MS is screwing its customers. So she gets her xbox modded before she gets on XBL. Sally makes sure that her huge replacement harddrive is clean and any "additions" she makes to it are located on F drive. This may not matter at all, but Sally thinks it's safer. Sally signs up with XBL for the first time and now her EEPROM and HDD serials are recorded. She's safe and Johnny is out in the cold. Johnny's sad.
That's pretty much the only way I can imagine it being. I never downloaded the Halo2 leak... I think its wrong. The only thing I have on my Xbox is a 200gb HDD with EvoX, XBMC, and my personal game backups. I'm banned. I'm never getting back on XBL anyway unless MS drops this stupid crusade.
The solution is this: Get another HDD, another EEPROM, and a brand new XBL acct. Then follow ClockedHunter's directions. It seems to be the most reliable fix thus far.