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.