Despite your previous internet quality test, it's possible that your connection is intermittently bad. Who is your internet service provider?
If there is some repeatable pattern to this, such as calls to/from a particular phone number or location, that might help.
Which internet telephone service provider are you using? You mentioned the Google Voice firmware issue, but you didn't specifically say if these calls are over Google Voice (technically, Google Chat)?
On some GV calls, GV will (re)negotiate the CODECs being used between carriers, during the first few seconds of the call. In those cases, it's possible to hear degraded sound.