I'm not sure why you remember MS the way you do. There was a much much larger barrier for consumers to move to a different OS. If you owned a PC you pretty much had to run Windows. And MS made it extremely difficult to use a non-IE browser in the OS.
That doesn't mean I think they're innocent in all things but I don't see how their search market share is a monopoly target.