Why do Americans care so much about recommendation letters?
I think Bryan's answer gives a nice perspective on the issue. A perfect system does not exist, and different continents have developed different (imperfect) ways of dealing with the fundamental recruiting problem that it is hard to judge whether a specific student (or employee) will perform or not.

What I want to add is that, if you peek behind the covers, the European and American systems don't actually differ all that much. You assert that in Europe "your CV is all that counts". That is, unfortunately, quite naive. The CV of your average student is simply not expressive enough to be "all that counts" - good grades are at best a weak indicator of research potential, and (despite your counterexample from France), also in many places in Europe many students have very good grades, to the extent of being low-value as a discriminator in hiring. Grades also do little to measure the soft factors such as motivation or being a good team player, which ultimately matter more than whether a student had an A or a B for some largely unrelated undergrad course.

How professors in Europe largely have dealt with this uncertainty is by personally asking the professors that the student worked with before what their impression of the student was - so you still have your "recommendations", but not through written letters but through informal email or telephone exchanges. This was possible because traditionally, students in (at least central) Europe were not particularly mobile - most prospective PhD students did their undergrad in the same university, a close-by university, or a different university where the professors are already in close contact. Applicants from other places were often rejected outright. Now times are (slowly) changing and more and more PhD students come from abroad - and, lo and behold, suddenly formal recommendation letters are becoming important as well.

Another aspect that I am missing in your question that at least central and southern Europe has historically had a problem with rampant nepotism in academia. So I find it particularly curious that you draw Europe as a haven of objective hiring strategies.