A common misconception. When spamming sites are removed from the index, the actual number of results per SERP does not decrease, but remains the same. The gaps are filled by those sites whose user-visible content DOES match the search query. When spamming sites are removed from the index, they get replaced by sites the searcher was looking for. So AFTER the removal users find information which they could not find before.
If I am looking for a used car (one of the German keywords that bmw.de was cloaking for), I want to find portals or websites where used cars are sold. I do not want to go to a site of a company which only manufacturers new cars, it has no added value for the searcher. According to one of the sources on the net which revealed the BMW cloaking, on one of the user visible pages the German equivalent word of "used car" was mentioned only twice, where the cloaked version mentioned it 42 times.