Sorry for breaking the thread, but I have just joined the list.
You don't need the same client on Windows and Linux. I would use SIP
phones since I have found them the most reliable and the most
widespread. That will change as IAX becomes the norm (I think).
There are two ways that I communicate with my Windows/Mac friends.
Either is OK.
1) Both of you establish and account on Free World Dialup:
http://www.freeworlddialup.com/
On Linux, use Ekiga. Ekiga will connect to multiple accounts, so you
can have your Ekiga account and your FWD account active at the same
time.
On Windows/Mac, use the Sjphone: http://www.sjlabs.com/
It is a very good sip-phone. The one for Linux is good too, but it is
not free software and it does not connect simultaneously to multiple
accounts.
2) Both of you establish an account on
Gizmo:http://www.gizmoproject.com/
The Gizmo client for Windows is excellent. You still can use Ekiga on
your Linux box, and I recommend that you do so. I speak to my daughter
frequently with this Gizmo-Ekiga combination and the sound is excellent.
It is not necessary to use the Gizmo client to connect to the Gizmo
network. Your friends can use the SJphone if they prefer. You can use
Ekiga.
There are any number of SIP based systems out there that you can
subscribe to. The two I mention are just ones that I know well.
It is not strictly necessary for both of you to be on the same
"network", but it is convenient. Most networks have "peering"
arrangements that allow you to connect easily to other networks. See
also SipBroker: http://www.sipbroker.com/sipbroker/action/login