It's not really straight from the manufacturer is it?

I'm not sure about how Vodafone works, but most carriers around here love to brand their phones. The issue it self seems to be isolated to just the Vodafone models so could it be part of the branding they do with the phones?

You can choose when installing AVG under the custom install not to install the search protection at all. Your AVG icon won't show that there's an error and you don't get the ridiculous slow down while searching.