Could it be the codec?
Is it possible Vodafone uses a different codec? For instance, AT&T sounded **HIDEOUS** for years here in the US in most markets. They were using AMR-FR (full rate) in just a few markets, and AMR-HR (half rate) *all the time* in most markets. T-Mo at that point was usually running AMR-FR (full rate) with half rate used only if the site was busy, and then only if your signal strength was good enough (i.e closer to the site -- since half rate has poorer error correction, calls would go back up to full rate further from the site.) AT&T apparently got over this more recently. T-Mobile now advertises "HD" calls, running I think 14kbps codec (which is a little higher than the usual AMR-FR.)
I won't compare with Sprint and Verizon, the CDMA codecs are quite different, and there is no defined "half" and "full" rate on this setup. It's still possible to tank call quality by setting average call bit rate too low though.