The link you've given shows Google had the majority of market share by October 2004, which is in line with what the parent comment states (at least the way I parse it).
What were they paying to be default on prior to October 2004? Smartphones didn't exist, Firefox didn't exist, Internet Explorer didn't have a dedicated UI element that led you to a search engine.
Are we talking about software that made Google the default home page? IE Toolbars? Feature phones like the Blackberry?
I was active on the Internet since the late 90s, but I only remember having to type "www.google.com" prior to 2005, but I'm certainly no means an expert.
[1] https://datahub.io/rufuspollock/search-engine-market-shares