Contact no longer showing in list, but can still speak to them if they contact me first

A few days ago one of my contacts stopped appearing in my contacts list. I can't contact them, but I still appear in their list. If they contact me, then we can chat just fine. Their Skype status shows a ? while we're chatting.

Any ideas how I can fix this or why this is occurring? I thought it might be an update, but they say they haven't done anything - can this happen silently?