[RMD]

I use KK's Loaded Rom, but I usually setup Hotmail via the "Windows Live" app.
Are you doing it this way as well?
I've never had this problem and it's the first thing I do after restoring my data.

The app should create the Mail account for you.