If there is someone else (typically someone who has respected enough deadlines to be appointed professor) who also thinks you deserve a PhD, then fight.
Your main concern seems to be finding a job in Germany. Now, for academic positions, you're going to need that PhD. For organizations outside academia, your 3 years of research will have little value (unless you were an employee of the university as a Wissenschaftliche Mitarbeiter in which case you can claim some sort of experience, but my guess is it's not the case as it sounds that you are not even in the country). In fact, as an employer, I would be reluctant to hire someone who managed to fail enough administrative requirements to find himself in your current situation, regardless of the possible mitigating circumstances.
These employers will consider your current highest degree, should you decide to apply without getting a PhD, don't make too much publicity about your failed attempt at getting a PhD. Instead, present it as independent research, your publications might help depending on the field, but usually won't.
Applying to another PhD program will mean starting everything from scratch, it's unusual for universities to let people walk in with 3 publications and a thesis and ask for a title. Whether you are ready to invest 3-4 other years of your life for that is a personal decision.
To conclude, if you can get support form someone inside the university (someone I would be tempted to call an advisor, or supervisor, but I would refrain myself due to the apparent inadequacy of such a concept in this context) who is a faculty/habilitated/a professor, and is convinced that your work is worth a PhD degree, I would recommend to do everything in your power to have the administrative authorities allow you in.
Note: there is a lot of guesswork to do with your question, here is my take, although my interpretation might not be shared with many other users of this site.