My guess is that MSN servers are having glitches again.
Something they could be using is Stuffplug NG wich has the feature "talk to blocked contacts". This means nothing else than that they blocked you (so you see them offline) but can still message you.
But as you say normally those contacts are online so lets keep it at serverglitches
/ 
