No momento, não é possível tornar seu perfil "privado", o que basicamente faria o que você deseja. O Skype permite que certas partes do seu perfil permaneçam privadas, como sua idade ou local, mas o nome e o endereço de e-mail são públicos (ou, pelo menos, pesquisáveis).
Nos fóruns do Skype:
Your profile information cannot be completely hidden as it is used in the Skype directory so that people can actually find you. Similar to a phone directory. Some options are statically public. If you do not want that information to be public it would be best to keep it blank. My profile on all my accounts remain as blank as can be. If people need to find me in the directory I provide them with my Skype name or e-mail address. To view your profile information and edit it just press "Ctrl - I" while in Skype. It is less restrictive than editing your profile on the website.
Uma alternativa seria usar um endereço de e-mail de proxy e desativar as permissões do aplicativo no seu catálogo de endereços de contatos em seu telefone. Isso não é uma configuração no aplicativo, mas sim o sistema operacional do telefone.
Também é certamente possível que o Skype use sugestões "spider-web". Seus servidores procuram por amizades comuns e, da mesma forma, com o Facebook, sugere a pessoas que são mais matematicamente capazes de conhecê-lo. A única maneira de impedir que a Microsoft - ou qualquer rede social - faça isso (se estiver), é parar de usar o produto, já que eles não oferecem a opção de desativá-lo.