The law in question dates back to 1995
That's more than a bit disingenuous of you... the law has been around, but the court's rather bizarre interpretation of it, that it requires search engines to remove links but doesn't require the source sites to remove the content, is extremely new. A more reasonable interpretation is that if some information should be removed the target should get the source site to remove it, which will automatically cause it to disappear from search engines, given that they're mere indexes.
By your logic Microsoft never had a monopoly with Internet Explorer
Agreed. Microsoft did not have a monopoly on browsers. Actually, no court ever said they did. What the court said was that they had a monopoly on desktop operating system software... which is itself a questionable conclusion, but less so given the way Microsoft had the PC distribution channels locked up.
Monopolies are not determined by amount of competition, but by amount of marketshare held, so unless you're going to argue like a fool that Google doesn't hold the vast majority of marketshare then you can't argue that Google doesn't hold a search monopoly.
I don't think market share tells the whole story, especially with respect to something like web search, because the effort required to use a different search engine is basically zero. Using a PC operating system other than Microsoft Windows was much more difficult back when MS was in anti-trust court.
For that matter, Google's market share isn't that overwhelming. In the US it's only 68%. In much of Asia it's less than 10%. In Europe it's higher, granted, in excess of 80%, but that still doesn't overcome the ease-of-switching factor, IMO.