The record can exist and it might be a breach of someone's fundamental right to privacy to make that record available via data processing.
The ruling did not state that the record will not cease to exist or would not be accessible, but that data processing of the information could be a breach of the person's right to privacy.
Another example: Let's say Bob actually only did commit a very minor crime. In the EU the ability to rehabilitate is protected by law. Only certain government departments have the right to access certain classes of crimes on a criminal record after n years.
If you were to make a database of court judgements (nearly all of which are a public record of fact), and make available Bob's criminal record after n years had passed. You would definitely be in breach of the law.
This has existed in law for a long time and isn't completely illogical.
Read the ruling, it acknowledges records of fact and states that the right to process those records doesn't trump the fundamental rights.
It's why they're called fundamental rights and data processing isn't on that list of fundamental rights.
Google, as a search engine, performs data processing. That it holds the record wasn't touched by the ruling, but the press has mentioned "removed" when actually it is "don't data process" which has the effect of ensuring the record doesn't appear on a results page, but does not actually remove the record from existence.
Wikipedia says that the definition of processing according to the directive is: "any operation or set of operations which is performed upon personal data, whether or not by automatic means, such as collection, recording, organization, storage, adaptation or alteration, retrieval, consultation, use, disclosure by transmission, dissemination or otherwise making available, alignment or combination, blocking, erasure or destruction;"
Indexing is obvious. A library's internal index system does data processing. If it indexes it's own collection, it would appear to be subject to this ruling, so that a person could demand that they are removed from the library's index systems, while still remaining in the archive.
What about machine translation? That seems like retrieval and adaption. Do all generic translators have to have provisions for privacy?
Browsers do retrieval to render pages. Do browsers need a list of verboten web pages that they refuse to render?
Actually it makes perfect sense. Making it difficult adds a barrier. You don't have to make it impossible to prevent something from happening. Sure, you might not stop the most determined people, but you'll stop millions of cases by just making it harder.
It's not black or white -- as a lot of security people use to think for similar things like "security by obscurity" etc. Most of the time your adversary is not some highly capable entity, but just common folks who'd give up at the first barrier.