Is msn messenger 7 still installed? Have you tried removing it?
Have you tried reinstalling Windows Messenger 5.1
(they are not the same thing--and remote assistance requires Windows Messenger 5.1, but not msn messenger).
I have also found one example where reinstalling sp2 fixed the problem, but only by using a network installation