This issue is complex. What the Mehmet case illustrates is that the right offers up a symbolic solution (extradition) which it can't carry through. For instance, you can't deport a young Greek because he's an EU citizen, and you can't deport a young Turk who lives in Germany because of a treaty, signed at the EU level. It conflicts with EU law, it conflicts with the European Convention on Human Rights, and it probably also conflicts with the German Verfassung. So, it's never going to hold up, but yet the right keeps pounding its symbolic drumbeat of deportations. Purely for electoral purposes, in this case.

The issue is indeed complex; therefore, I don't believe it can be reduced entirely to Right-versus-Left terms, though there is that element to it as well as an "election campaign drumbeat"at the present time. It's certainly true that laws against deportation from Germany have been tightened in recent years, but close inspection reveals that in each new decision there are caveats allowing deportation after consideration of strict criteria applied to a particular case.

The Mehmet affair in Munich is a case touted as a purely Right-Left controversy; however, there were ordinary people of every political stripe in the Bavarian capital who applauded the deportation of Muhlis Ari, the young Turk's real name, and they regretted the Bavarian court decision allowing him to return to Munich. The case genuinely alarmed those who were concerned about violence and crime involving youngsters. Many a voice could be heard in Munich saying, "We have no choice but to deal with our own German offenders, but let's deport foreign citizens, who are not our responsibility." That widespread reaction in Munich is a fact, and there's no getting round it.

You wrote:

What I did find out in the mean while is that there is a large amount of debate among criminologists about which approach will work and that I am largely unqualified to comment upon it. If you have the time to read the wiki article on zero tolerance, you will find that it is (in some parts) written from a POV that is outright hostile to that approach.

German media over the years have reported visits of American officials invited to Munich to explain their success at home with zero tolerance. One such American was quoted in the German press as saying: "Why do you Germans put up all your signs banning this or that when you don't enforce the ban? What then is the good of a smoking ban on public transportation or a ban against riding a bicycle the wrong way in a one-way street?"  The Americans advocated strict enforcement of every single ban. Otherwise, they said, don't put up the signs.

Now there you leave out the essential part of the story. Beckstein did succeed in deporting him. Muhlis was sent to relatives in Turkey, where his case was noticed enough that he got a job in a music television. He spent IIRC two years there, before the courts allowed him back.

"Noticed enough?" Unfortunately, that's not the story (Wikipedia leaves out a lot).  The Muhlis Ari case became a cause célèbre for the Istanbul newspaper Hürriyet, which has a huge readership among Turkish-speakers in Germany, and in other Turkish media that spoke out regularly on his behalf. Therefore, a TV station in Turkey offered him a job as co-moderator of a music show aimed at teenagers when he ended up in Turkey initially as a deportee. The station was trying to cash in on his notoriety and publicity in Turkish media. German TV later showed excerpts of the Turkish show in which poor Muhlis was obviously totally out of his league. It wasn't hard for a viewer even to feel sorry for the brutalo, watching him bumble about the stage. It wasn't long before his Turkish TV colleagues started telling German correspondents in Istanbul that the station was going to drop him because he spoke primitive Turkish (his German is primitive, too), and he also wasn't able to learn the job. Then German correspondents learned that he was suspected of stealing equipment from the TV station, which decided to fire him with as little publicity as possible so as not to lose face.

It's better not to go into the details of some of the reports about the case carried by Hürriyet and other Turkish media. Such reports can only provoke resentment and more intolerance of Turks in Germany, where there's already enough of that. Just one translation into German already got some Germans' backs up. As a result of the translation, readers learned among other things that the logo in the masthead of Hürriyet says "Türkiye Türklerindir" (Turkey Belongs to the Turks), a historical slogan that nevertheless had some people asking whether the same doesn't hold true for Germany. Germany belongs to the Germans?

You wrote:

Another thing not mentioned is that these "foreigners" were/are foreigners only because of Germany's restrictive bloodline citizenship laws. In many other countries, being born there is reason enough for citizenship. This non-citizen status is certainly part of the problem.

Restrictive? Many countries, in Europe and elsewhere, have the same law as Germany. The law could be changed if there is a consensus for change, but a change should probably best come about within the EU framework, applicable to the entire union. The possibility of that is doubtful at this time.