The best way for free VoIP is probably going to be to setup your own service.
Something using free software on your own computer and you talk directly to another person on his/her own computer instead of having a online server handle the connections for you.
Trouble is that both of you'd have to have the same or at least compatable software installed on both machines.
With Linux you have a software implimentation of H.323, which is a standardized protocol for doing teleconfrencing over the internet. It's called OpenH323 and you'd have the ability not only to do voice, but transfer files, do e-mail type text messaging things, and do video. You'd use something like Gnomemeeting (for Linux) or Microsoft's Netmeeting to use it.
However something like that is more designed for when you have dozens of people in a office enviroment or whatnot.
There has to be a easy simple solution for it, but I don't know. Maybe something to with Jabber and you have a plugin for it? Maybe.
Maybe use something people use for gaming called "teamspeak".
I'll look up stuff and see what I can find.