Updated March 2014: http://howden.net.au/thowden/2014/03/internet-explorer-and-google-search-provider-australia/

With the updates to Internet Explorer through version 9 and 10 one of the things that Microsoft has apparently lost is the ability of IE8 users to add Google through the default options.

Searching the web will provide all manner of advice on installing Google as a Search Provider using the Manage Search Providers option which leads to the Manage Add-ons page and a link to Find More Search Providers…  which opens up http://www.iegallery.com/en-au/addons?callback=true&featuretype=2

The link used to provide a number of options including Google as a Search Provider and an option to manually Create Your Own Search Provider, but this is no longer the case. In fact the list of search providers includes 2 options for Bing (why?) and eBay Australia Search option. Now conspiracy theories aside, it is apparent that Microsoft will not actively promote Google but it is pretty damn obvious that they have made it damn near impossible to add Google.

So I have an older computer with XP on it and I am not about to upgrade and I persisted with searching through the 3 year old forums and finally found a direct link to a page.

http://www.iegallery.com/en-US/Addons/Details/813

And for as long as this Microsoft page is active the install of Google as a search provider is resolved.  But finding that page through any of the normal processes just does not work.