I had several old names that I no longer wanted in my phone book showing up under the filter “Microsoft Messenger.” Googling around revealed that several others had this issue. My solution was anything but straightforward, but here was my experience:
I downloaded the legacy version of Messenger (ignoring any incompatibility warnings), logged in from there, and removed all of the contacts from my PC while I had my phone off. I uninstalled Messenger, restarted my PC and turned my phone back on. The contacts were still there.
Annoyed, I turned my phone back off and reinstalled Messenger to see if I’d missed anything. I noticed that this time, it wouldn’t let me log in and instead demanded I upgrade Messenger. I clicked “okay”, but the update failed because it wanted to upgrade Messenger to Skype, which I already had installed. So, I opened up Skype on my PC, incidentally(?) deleted a couple contacts I no longer was in touch with from that list, and closed it.
At this point, the unwanted “Microsoft Messaging” contacts were no longer appearing on my phone contact list.
Windows Phone is great for all my needs, but I am finding a number of little kinks like this along the way that might scare away other users.