Yeah, these all sound like the problem i'm experiencing.

I tried deleting the msn account from the phone and re-adding it. This just led to msn re-adding all my contacts in my contacts list, but not when you press the new IM button. Now my contact lists very untidy, as people have their own original contact card with their msn address in it, plus a new seperate entry for just the newly re-added msn contact, which annoyed me greatly and didn't solve the problem