Pelo menos nas versões anteriores, tive sorte ao criar várias cópias executáveis do skype.exe e, em seguida, executá-las em diferentes contextos de usuário usando o recurso "troca rápida de usuário" do XP.
Nesse szenario, o usuário A iniciou automaticamente uma cópia do executável e o usuário B iniciou um diferente. Ambos os usuários efetuaram login simultaneamente. Ambos podem usar o Skype. Ocorreram problemas, é claro, quando uma sessão de usuário com uma conversa ativa no Skype foi trocada e o outro usuário tentou usar o Skype para comunicação. Tudo funcionou bem, se bem me lembro.
E observe que, no meu cenário, os dois usuários tinham seus próprios desktops. Não tenho certeza se seria o suficiente para usar o RunAs ou um utilitário similar de execução de comando como um usuário diferente.
O bom é que se isso funcionar com a versão atual do Skype, ele também funcionará para mais de dois usuários (em oposição à sugestão de variante portátil).