Let me start by saying that I am by no means an expert on VoIP on the Nokia E61. I probably only know the very top of the VoIP iceberg. When I first got my Nokia E61 I tried to use the VoIP functionality but couldn't get it to work. I spent a few days trying to set it up but to no avail. I soon lost my patience and forgot about it. I focused on the many other features and applications available for the Nokia E61.
Set-up problems aside, another reason I lost interest is probably that I am not the right target for VoIP. I have a calling plan that provides me with more minutes than I can use and if that isn't enough, all weekends and evenings are free.
As is common, long distance or mobile-to-mobile doesn't matter since the effective price per minute is the same with my carriers' plan. For international calls I rely on prepaid telephone cards - I dial a local number, dial my pin code and then the international call I want to make. This way the cost for an International call drops to a cents per minute.
However, VoIP on the Nokia E61 is one of the most common questions I receive so there is clearly a large interest and demand for this feature. A week ago I thought I should give VoIP on the E61 another chance. I came across two services/sites that I liked - Sipgate and VoXaLot.
I like these services because they have removed ALL the issues I had of setting up VoIP on the Nokia E61. Both Sipgate and VoXaLot has excellent support and documentation to make their services work on the E61.

Sipgate let's you sign up for a German or UK (if you live in the UK) telephone number so that you can receive phone calls. Naturally, you can also call other Sipgate users for free. Their wordwide rates are also reasonable.
One reason I really like Sipgate is that as soon as you have registered as a new user (free) and signed in, Sipgate will generate all your personaliazed settings and display them on a webpage complete with screenshots for each of the set up steps on the Nokia E61. You will see each step of the set-up with your personalized settings as it should appear on your Nokia E61. With this brilliant set-up you CANNOT GO WRONG!
Simply register and sign in and you will see your own settings:

VoXaLot doesn't have the same personalized set-up page but it is as easy to set up. Thanks to very clear direction posted by Martin you can register and get it to work within a few minutes.

(Press in the joystick to get the selection screen below, in order to make an Internet call)

Another nice touch by VoXaLot is that voicemails you receive to your account will be forwarded to your email address as an attachment. Naturally, you can also dial in to pick up your voicemail but the added service to have them sent via email is very convenient.

In addition to Sipgate and VoXaLot, there are many good "how to use VoIP on the Nokia E61" posts available. Pasha over at NokMe has written a great guide of how the set up of Nokia E61 for pbxes and Gizmo. There is also good information from Christian about using Nokia E61 with Asterisk. Last but not least, Martin has posted about using the Nokia E61 with FON.
So many VoIP solutions for the Nokia E61 - so little time…