I've had really good luck with Callcentric as my VOIP provider, using just a pay-as-you-go plan for my international travels. Overall excellent connections and responsive service.
As a softphone, I've connected with SJPhone with good results, but most of the time now just connect with my Nokia E65 to Callcentric. As you can sign up on Callcentric for free and download the SJPhone for free you can give it a try with no cash outlay and see if you like the results.