Just to chime in with my findings.
I had a modded xbox, I reverted back stock (old hard drive, removed chip entirely) on 11/9/04. I called M$ because I couldn't sign in to XBL. They said my account was in good standing and I just need to do an account recovery. I did that, and it worked. Wheeeee!
So we had a big LAN party last night, I tried out XBL, and it worked fine. I get my box home today and try to go on live, and says I'm banned. They say I should buy another xbox and hung up on me.

So to review:
Stock hard drive
No Mod chip
Haven't previously play XBL for months
Never been banned
M$ said GamerTag was in good standing
WTF??? I just got Halo 2, and can't do crap with it. Grrrrrrrr.