We already make exceptions for certain things (illegal content). Obviously a line has to be drawn somewhere - it's just a matter of where we draw it.
>> "We, the users, are missing out on the completeness of our search results."
With this law AFAIK content cannot be removed if that would be against the public good. So, for example, a politician can't have an article that makes the look bad but is true removed. Technically, although no longer 'complete', the quality of your search results should not be hit. The only results being removed are ones which are incorrect and damaging to someone.
>> "If you don't like it, take it up with the publisher."
AFAIK with this law the publisher has to remove it too. Google is involved because they cache pages which can include deleted content.