Protocols

SIP is the main standard, and is open. Different SIP clients can work together, however due to codecs differences and other aspects, this may not always work. SIP is more modern than H323 (an older standard) and is probably the best choice right now (March 2009).
Work is in progress to add VoIP (audio / video support) to the XMPP (Jabber) protocol through the Jingle project.
A SIP account can be obtained for free at ekiga.net. Note that Free gives you a SIP account (freephonie.net), however they do not always obey to the SIP specifications and some clients cannot work with this account. On the other hand, other clients have trouble connecting to ekiga.net...
Firewalls can be problematic so some applications will use a STUN server to work around NAT issues. Ekiga seems to work fine, other applications are not always able to do this correctly apparently.
Also, applications under VirtualBox seem to have more firewall related problems, even when using bridged mode.

SIP

You cannot seem to have two applications registered to the same SIP account at the same time (it probably depends on the server settings, of course). Note that Ekiga does not unregister its session when quitting (you have to manually do it in the Accounts window).
An outbound proxy is the server used to make outgoing calls.
The best codec seems to be G711 (u-law / A-law). UPDATE: the best codec seems in fact to be G729, but it is not a free codec.

There are three methods for sending DTMF tones. Not all of them are supported on every client:
- Inband (the tone is sent via the audio flux)
- RTP (RFC 2833)
- SIP INFO

On Mac OS X Ekiga is unfortunately not available. X-Meeting should be used but it seems much more buggy than Ekiga.
GoogleTalk will add support for SIP at some point.

To get debugging ouput under Gentoo, Ekiga and associated libraries must be built with the debug USE flag (that's not only for internal gdb debugging).
To get DTMF support (the ability to send tones via the dialpad), you must build Ekiga and its libraries with the dtmf USE flag. It does not seem to work very well (with every system) yet though. If you press a key on the dialpad while Ekiga was not built with DTMF, I had a very strange error (every call would later result in "Security Check Failed"). The error goes away after some time.

Twinkle is still based on Qt 3, and has such is ugly and currently have a problem with KDE 4 preventing the application from minimizing to the system tray.
Apart from that, it looks more mature than Ekiga. I had fewer problems when calling via Localphone.com VoIP provider (calls are getting disconnected though).
It is now masked in Portage so is not a long term solution unless a new version (KDE 4 native) appears.

OVH does not support DTMF via RFC with a G711 codec (and I am not sure SIP INFO works everywhere, so this is problematic).
OVH supported codecs:
- G711 (a/u)
- G723
- G726
- G729

For conferences (eg, more than 2 people) a server should be used, with each peer obtaining a connection to the server.

There are many closed protocols and applications. Skype is one of them. It is easy to setup and works relatively well, but the Linux version is not the same quality as the Windows one.
MSN, iChat etc also use closed protocols which makes the use of audio / video hard with them.