The question was raised it is really about low bandwidth, as low bandwidth issue may be easily solved by using better codec or lowering a quality of transferred voice to reduce number of bytes required to transfer.
More difficult to deal with is another issue - low quality connection. If connection has low quality (frequent packet drops or very long ping time), then communication over this connection appears to users as worse than in case of connections which have a low bandwidth.
A solution was proposed, to use some kind of push-to-talk software, which would record a message (voice message), send it to recipient which could then play it. This way quality would be better, but converstation speed would drop.