I just come back from an Egypian in Germany who wants to talk per VoIP to his family in Egypt. In Egypt they used a good PC, Windows XP and MSN Messenger 7.5 on a 56k-modem. (They are waiting for DSL)
We had a laptop with only 64 MB RAM, Windows98 SE and MSN Messenger 7.0.
Sound quality from Egypt (modem only) to here was OK. They reportet the same back.
That means:
The codec in MSN Messenger 7.x does it fully! Sorry, but I don't know which one they took.