You've encountered regular pauses when sending or receiving sound and, to cope with the problem, enabled GSM, LPC, CELP, or LPC-10 compression to reduce the data rate. But the problem got worse-- more audio was lost with compression than without! What's going on?
This indicates that not only isn't your network connection fast enough to transmit audio in real time, your computer can't compress it into something your network can send quickly enough to keep up with the audio input.
Short of replacing your computer with a faster machine which can perform compute-intensive compression in real-time or obtaining a faster connection to the Internet, the only options are to try ADPCM compression or to see if also enabling both Simple compression with the Options/Connection menu item works. By discarding every other sample, Simple compression halves the amount of data another algorithm must process in a given time period.
The performance benchmark can help determine which compression modes are within the computing power of your machine.