Is it possible? Yes.
Is it practical? Not so much.
If your contact has a Microsoft account that they previously used on Messenger that has you on their contact list, they can sign into Skype using that account, then link their existing Skype username to it and you’ll both be able to talk to each other on your own client.
The problem begin if they don’t use a Microsoft account and/or never added you to Messenger on that account. Messenger contact lists on Skype are read-only, so the primary problem to resolve is getting you on their Microsoft account’s contact list. Previously this was pretty easy to deal with, as it just required a few clicks in Hotmail/Outlook.com to add a contact. Unfortunately Microsoft removed this feature sometime in the last six months and so now you need to use a real Messenger client to add contacts.
The process is the following, your contact needs to:
- Create or have a Microsoft account
- Sign into a real Messenger client using that account
- Add your Messenger account to their Messenger account (or vice-versa and just accept the add invitation)
- Confirm you’re able to communicate through Messenger
- Sign into Skype using that Microsoft account and if it’s not already linked to their existing Skype username, then link it
You then would be on their Skype contact list and they would be on your Messenger contact list.
Although I’ve tested this significantly and have known others that have gone through this process (especially when it was easier to do), I never made any of my contacts go through this. Even though I have a fair share of Skype users on my Messenger contact list, I try to keep Messenger and Skype separate and use the Skype client to communicate to them.
Just a final note since you mentioned it, Messenger works just fine on Windows 8, 8.1 and even the Windows 10 betas (so far anyway).