This is what I was seeing after adding a colleague on Skype... Offline, always offline.
Following the advise of the article above I had to ask that colleague to add me using a different email address. Example: if your Skype sign-in email address is [email protected], you should be looked up by cooldude(mail.com)@msn.com.
Doing that worked like a charm for one of the contacts I've added. However most of the others got this instead...
For some reason Lync (Skype for Business) was saying that I was blocked. Strange, but not a big deal. Right-clicking my contact and adding me to a group in the contact list seemed to have unblocked me.
After doing all that, I was able to see the added contacts as 'Online' and more importantly - communicate with them.
Remember this will only work if your Skype account is linked to a Microsoft account.