I'm also getting this problem, my contatcs sometimes see me as offline, or thier messages fail to send to me a hell of a lot.
Me and my gf have resorted to talking via email/AIM when we arnt with eachother irl =/
Its uber annoying
I'm guessing its a server problem, though it could possably to do with plus? Since so far I'm assuming everyone Ive seen thats had this problem also has plus installed and msn 7.5.xxxxx installed.
eph.