Crazy possibility - Password too long
Hi piratepratt,
I had a similar problem a few days ago. It solved when I changed my 19 digit password to a shorter one. For some strange reason, my iPhone 4 and iPod Touch started showing "Unable to verify account information" (Mail App) and "Wrong ID or Password" (MSN Messenger) messages. Seems like my phone couldn't send the whole password, because it was too long.
This used to happen with all apps that had to do with hotmail. Even the MSN Messenger App didn't work until I shortened my password to 14 digits.
Hope this helps, 'cause nobody seems to realize this tiny detail.
Good luck.