I have the exact same problem. Contact and Email sync works fine, but I cannot sign into messenger on ANY Windows Mobile device (I've tried my own HTC Touch, my coworkers' Touch, and another friend's Mogul).

But they can use my phone just fine. It must be my Live account.

Microsoft called me today and said I should just make a new account, but I find that unacceptable that I should have to change my email address.