Wie @juliankpf bereits anmerkte, wäre eine Untätigkeitsklage nicht die schlechteste Idee. Habe ich auch schon überlegt.
Meine Befürchtung: Vor dem Verwaltungsgericht Berlin wird sich das über Jahre hinziehen.
Ich kenne keine einzige Berliner Behörde, die auch nur ansatzweise etwas in einem akzeptablen Zeitrahmen schafft. Und das liegt nicht nur an mangelnder Personal- und Sachausstattung.
Nicht mehr lange, dann dauert die Beantragung eines neuen Personalausweises in B. länger als dessen Gültigkeitsdauer. 
Von meinen Anfragen wurden zudem inzwischen 50% beantwortet. Dazu habe ich eine Auswertung angefertigt (Anfragedauer in Tagen bis zur Beantwortung).
Die Trendlinie deutet eine Verbesserung seit meiner ersten Anfrage vor 2 Jahren an. Die unterhalb der Trendlinie liegenden Anfragedauern betreffen überwiegend Betriebe, die in den vergangenen 5 Jahren bzw. seit Betriebsgründung nicht überprüft wurden.
Auf ihre anfangs eingeforderte Antrags- und Identitätsbestätigung (Rückmeldebogen) verzichtet die Behörde nun. Eindeutig eine Verbesserung. Auch wenn es noch reichlich Verbesserungspotential gibt, wird dort im Gegensatz zu beispielsweise Treptow-Köpenick gearbeitet.
Ohne permanente Nachfragen funktionierte das aber auch in Friedrichshain-Kreuzberg nicht. Dafür nutze ich übrigens bevorzugt Faxe: Sie werden von FragDenStaat nicht limitiert (max. Anzahl von Erinnerungen pro Tag/Woche), lassen sich dort leicht dokumentieren, sind über einen entsprechenden Router kostenfrei, landen nicht “versehentlich” im Outlook-Papierkorb und nerven Behörden – hoffentlich – maximal.
Eine detailliert dokumentierte Untätigkeitsklage findest du unter Notes From The Field: Landkreis Osterholz. Ebenfalls dort zu finden: Eine Kurzübersicht über die VIG-Performance Berliner Bezirksämter.