Se você puder poupar algum dinheiro eu sugiro comprar um VPS em algum lugar onde o Skype não esteja bloqueado (por exemplo, Linode VPS em Londres) e então se você for usuário linux apenas conecte seu VPS e execute skype através desse túnel. Você pode encapsular através da porta conhecida (ou seja, 80), então isso deve passar descoberto através do provedor de internet.
E bom sobre VPS - você pode construir muito mais sobre ele, seu próprio servidor de e-mail, servidor http, e-robot, o que você precisar.