Xbox Live accounts are associated with a Windows Live ID (formerly MSN Passport I believe).
If you had a Hotmail email account, a MSN/WL Messenger account, or a MSN Passport from some other MSN service prior to the registration of your Xbox Live Gamertag, you probably associated your Xbox Live account with that (now) Windows Live ID.
A quick search reveals that it is also possible for Windows Live IDs to expire from lack of use, even if that Windows Live ID is associated to an active Xbox Gamertag. Please see Major Nelson's blog post for more details on that possibly related issue.
I recommend you A) try logging-in with any Windows Live IDs you may have used at the time you registered your Xbox Live gamertag, or B) use the Xbox with has your gamertag saved to it to change your associated Windows Live ID.
Best of luck getting your account sorted out.