Você está no caminho certo: você precisará de um provedor SIP, como o Skype, apenas com softwares e extras melhores.
Como tenho experimentado com eles, a maioria dos provedores SIP são internacionais. Eu tenho usado o FreeCall há algum tempo. Os preços estão bem, quase sempre disponíveis, o software deles não é ruim, embora eu use quase exclusivamente o cliente baseado na web.
Em casa, tenho um roteador VoIP (AVM Fritz 7270) que escolhe de forma transparente o provedor SIP correto, dependendo do número que está sendo chamado.
No meu dispositivo móvel (Nokia N97), eu instalei o aplicativo Symbian (também disponível para Android e iPhone) para fazer chamadas telefônicas, usando os contatos do telefone sem problemas. Estou ansioso para ver uma atualização que permitirá enviar mensagens de texto (SMS).