Sachverhalt: A. X._ wurde am 2. Juli 1986 vom Strafgericht des Kantons Basel-Stadt wegen Sexual- und Diebstahlsdelikten zu einer Gefängnisstrafe von 2 1⁄4 Jahren verurteilt. Gleichzeitig ordnete das Gericht eine ambulante psychiatrische Behandlung für die Dauer des Strafvollzugs an. Die Sexualstraftaten beging er an insgesamt 25 Mädchen im Alter von 7 bis 17 Jahren. Er betastete sie am Geschlechtsteil, zwang sie zu Zungenküssen, zeigte ihnen sein Glied, deflorierte ein Mädchen mit der Hand und zwang eines zum Oralverkehr. Teilweise verwendete er ein Messer oder drohte verbal. Am 11. Januar 1989 verurteilte ihn die Polizeigerichtspräsidentin des Kantons Basel-Stadt wegen fortgesetzter unzüchtiger Belästigung zu vierzig Tagen Haft. Ein weiteres Urteil erging am 21. Juni 1991. Das Appellationsgericht des Kantons Basel-Stadt verurteilte X._ wegen fortgesetzter Unzucht mit einem Kind und fortgesetzter Nötigung zu einer Zuchthausstrafe von 6 1⁄2 Jahren und ordnete eine ambulante Massnahme für die Dauer des Strafvollzugs an. Dem Urteil liegt folgender Sachverhalt zugrunde: X._ zwang ein 12-jähriges Mädchen zu diversen sexuellen Handlungen einschliesslich des Geschlechtsverkehrs unter Androhung von Gewalt mit einem Messer. Zudem fasste er einem 15-jähriges Mädchen in schmerzhafter Weise an die Brust. Am 12. Januar 1996 verurteilte das Obergericht des Kantons Zürich X._ wegen versuchter sexueller Nötigung sowie mehrfacher sexueller Handlungen mit Kindern zu 3 Jahren Zuchthaus. Es schob den Vollzug zugunsten einer Verwahrung auf und ordnete gleichzeitig eine vollzugsbegleitende ambulante Behandlung an. Die Straftaten beging X._ im Rahmen des Arbeitsexternats, welches ihm aufgrund einer Vollzugslockerung gewährt wurde. Dabei versuchte er ein 10-jähriges Mädchen unter Todesdrohungen zu zwingen, sein Glied in den Mund zu nehmen. Einem weiteren 11-jährigen Mädchen griff er an die Brust und zwischen die Beine, einem 13-jährigen Mädchen an die Brust. B. Infolge der Revision des Allgemeinen Teils des Strafrechts überprüfte das Obergericht des Kantons Zürich auf Antrag des Amtes für Justizvollzug die Verwahrung von X._. Mit Beschluss vom 25. Februar 2009 hob es die Verwahrung auf und ordnete stattdessen eine stationäre Massnahme nach Art. 59 Abs. 1 StGB an. C. Die Oberstaatsanwaltschaft des Kantons Zürich erhebt mit Eingabe vom 26. März 2009 Beschwerde in Strafsachen. Sie beantragt, den Beschluss des Obergerichts aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. 