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 <ref-law> 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.

Erwägungen:
1. 1.1 Die Beschwerdeführerin macht geltend, die Vorinstanz verletze <ref-law>, indem sie trotz nur minimal möglicher Verbesserung der Legalprognose die altrechtlich angeordnete Verwahrung aufhebe und an deren Stelle eine stationäre Massnahme anordne. Die Voraussetzungen für eine stationäre therapeutische Massnahme seien nicht gegeben. Nach 20 Jahren Therapie, wovon 10 Jahre in intensiver deliktsorientierter Gruppen- und Einzeltherapie stattgefunden hätten, bezeichne das aktuelle Gutachten die Rückfallgefahr des Beschwerdegegners nach wie vor als moderat bis deutlich. Auch bei weiteren Therapieanstrengungen könne mit einer Behebung der psychischen Störung und der strukturellen Rückfallgefahr kaum gerechnet werden. Die präventiven Möglichkeiten der deliktsorientierten Arbeitsweise seien ausgeschöpft. Der Gutachter stufe den Beschwerdegegner weiterhin als gefährlich ein. Eine bloss minimale mögliche Verbesserung der Legalprognose genüge nicht, um eine stationäre Massnahme anzuordnen. Vielmehr sei dazu eine hinreichende Wahrscheinlichkeit einer deutlichen Verringerung der Gefahr der Begehung weiterer Straftaten erforderlich, welche vorliegend fehle.
1.2 Die Vorinstanz führt aus, eine stationäre therapeutische Massnahme im Sinne von <ref-law> sei anstelle der Verwahrung nach <ref-law> gegenüber einem gefährlichen, psychisch gestörten Täter anzuordnen, wenn die hinreichende Wahrscheinlichkeit bestehe, diese Massnahme werde die Gefahr weiterer Straftaten im Zusammenhang mit der psychischen Störung innert fünf Jahren deutlich verringern. Sie zeigt die Entwicklung des Beschwerdegegners anhand der seit dem Jahr 1986 erstellten Gutachten und Therapieberichte ausführlich auf. Die Persönlichkeitsstörung habe sich stabilisiert und es gebe Hinweise auf positive Veränderungen risikorelevanter Persönlichkeitsmerkmale trotz zeitweiser Stagnation in der Entwicklung. Gestützt auf das aktuelle forensisch-psychiatrische Gutachten vom 19. Mai 2008 geht die Vorinstanz davon aus, dass vom kooperativen und motivierten Beschwerdegegner weitere Therapiefortschritte erwartet werden könnten. Die Möglichkeiten seien noch nicht ausgeschöpft. Auch wenn unklar sei, ob ein Restrisiko für weitere Straftaten überhaupt je therapeutisch angegangen werden könne, seien erhebliche Entwicklungsschritte zu verzeichnen. Das Rückfallrisiko sei gesunken und dem Beschwerdegegner hätten begleitete Urlaube bzw. Ausgänge gewährt werden können. Dass es bis zum angestrebten Ziel ein weiter Weg sei und nicht mit Bestimmtheit gesagt werden könne, ob das Ziel letztlich erreicht werde, schliesse die Anordnung einer Massnahme nicht aus. Diese sei in einer geschlossenen Vollzugseinrichtung durchzuführen und könne bei Bedarf letztlich unbeschränkt verlängert werden. Das Gesetz biete wirksame Möglichkeiten, um auf Veränderungen zu reagieren. Gestützt auf das Subsidiaritätsprinzip sei anstelle der Weiterführung der Verwahrung eine stationäre therapeutische Massnahme anzuordnen.
2. 2.1 Gemäss Ziff. 2 Abs. 2 SchlBest. StGB überprüft das Gericht bis spätestens zwölf Monate nach Inkrafttreten des neuen Rechts, ob bei Straftätern, die nach den Artikeln 42 oder 43 Ziffer 1 Absatz 2 des bisherigen Rechts verwahrt sind, die Voraussetzungen für eine therapeutische Massnahme nach Art. 59 bis 61 oder 63 StGB erfüllt sind. Trifft dies zu, so ordnet das Gericht die entsprechende Massnahme an. Andernfalls wird die Verwahrung nach neuem Recht weitergeführt.
2.2 Die stationäre therapeutische Massnahme zur Behandlung von psychischen Störungen ist in <ref-law> geregelt. Ist der Täter psychisch schwer gestört, so kann das Gericht eine stationäre Behandlung anordnen, wenn der Täter ein Verbrechen oder Vergehen begangen hat, das mit seiner psychischen Störung in Zusammenhang steht (Abs. 1 lit. a), und zu erwarten ist, dadurch lasse sich der Gefahr weiterer mit seiner psychischen Störung in Zusammenhang stehender Taten begegnen (Abs. 1 lit. b). Solange die Gefahr besteht, dass der Täter flieht oder weitere Straftaten begeht, wird er in einer geschlossenen Einrichtung behandelt (Abs. 3).
Eine stationäre therapeutische Massnahme nach <ref-law> ist nach der bundesgerichtlichen Rechtsprechung in Betracht zu ziehen, wenn im Zeitpunkt des Entscheids die hinreichende Wahrscheinlichkeit besteht, dadurch lasse sich die Gefahr weiterer Straftaten während der fünfjährigen Dauer des Massnahmevollzugs deutlich verringern. Die bloss vage Möglichkeit einer Verringerung der Gefahr und die Erwartung einer lediglich minimalen Verringerung reichen nicht aus. Es ist indessen nicht die hinreichende Wahrscheinlichkeit erforderlich, dass nach einer stationären Behandlung von fünf Jahren die Voraussetzungen für eine bedingte Entlassung aus der stationären Massnahme gemäss <ref-law> erfüllt sind. Bei Bedarf besteht die Möglichkeit der (mehrmaligen) Verlängerung der stationären therapeutischen Massnahme um jeweils fünf Jahre (<ref-ruling> E. 3.4.1 S. 321 f.; <ref-law>).
2.3 Das Gericht ordnet die Verwahrung nach <ref-law> an, wenn der Täter einen Mord, eine vorsätzliche Tötung, eine schwere Körperverletzung, eine Vergewaltigung, einen Raub, eine Geiselnahme, eine Brandstiftung, eine Gefährdung des Lebens oder eine andere mit einer Höchststrafe von fünf oder mehr Jahren bedrohte Tat begangen hat, durch die er die physische, psychische oder sexuelle Integrität einer andern Person schwer beeinträchtigt hat oder beeinträchtigen wollte. Kumulativ ist erforderlich, dass auf Grund der Persönlichkeitsmerkmale des Täters, der Tatumstände und seiner gesamten Lebensumstände ernsthaft zu erwarten ist, dass er weitere Taten dieser Art begeht (Abs. 1 lit. a) oder auf Grund einer anhaltenden oder langdauernden psychischen Störung von erheblicher Schwere, mit der die Tat in Zusammenhang stand, ernsthaft zu erwarten ist, dass der Täter weitere Taten dieser Art begeht und die Anordnung einer Massnahme nach Artikel 59 StGB keinen Erfolg verspricht (Abs. 1 lit. b).
Die Verwahrung von psychisch gestörten Tätern, bei denen längerfristig Heilungschancen bestehen, von denen aber kurz- oder mittelfristig im Vollzug oder ausserhalb der Anstalt eine erhebliche Gefahr ausgeht, ist nach neuem Recht nicht mehr möglich (<ref-ruling> E. 3.4.2 S. 130 mit Hinweisen). Sie ist angesichts der Schwere des Eingriffs in die persönliche Freiheit des Betroffenen "ultima ratio" und darf nicht angeordnet werden, wenn die bestehende Gefährlichkeit auf andere Weise behoben werden kann (<ref-ruling> E. 3.4.4 S. 131 f. mit Hinweisen). Dass der Täter auch in der Verwahrung psychiatrisch betreut wird, wenn dies notwendig ist (<ref-law>), ist kein Argument gegen die Anordnung einer stationären therapeutischen Massnahme, da sich die psychiatrische Betreuung im Sinne von <ref-law> prinzipiell von einer therapeutischen Behandlung im Sinne von <ref-law> unterscheidet. Die therapeutischen Massnahmen haben in erster Linie eine "therapeutische, dynamische Einflussnahme" und damit primär eine Verbesserung der Legalprognose zum Inhalt und nicht bloss eine Pflege, d.h. eine "statisch-konservative Zuwendung" (<ref-ruling> E. 3.6 S. 322 mit Hinweis).
Die Verwahrung von psychisch gestörten Tätern, bei denen längerfristig Heilungschancen bestehen, von denen aber kurz- oder mittelfristig im Vollzug oder ausserhalb der Anstalt eine erhebliche Gefahr ausgeht, ist nach neuem Recht nicht mehr möglich (<ref-ruling> E. 3.4.2 S. 130 mit Hinweisen). Sie ist angesichts der Schwere des Eingriffs in die persönliche Freiheit des Betroffenen "ultima ratio" und darf nicht angeordnet werden, wenn die bestehende Gefährlichkeit auf andere Weise behoben werden kann (<ref-ruling> E. 3.4.4 S. 131 f. mit Hinweisen). Dass der Täter auch in der Verwahrung psychiatrisch betreut wird, wenn dies notwendig ist (<ref-law>), ist kein Argument gegen die Anordnung einer stationären therapeutischen Massnahme, da sich die psychiatrische Betreuung im Sinne von <ref-law> prinzipiell von einer therapeutischen Behandlung im Sinne von <ref-law> unterscheidet. Die therapeutischen Massnahmen haben in erster Linie eine "therapeutische, dynamische Einflussnahme" und damit primär eine Verbesserung der Legalprognose zum Inhalt und nicht bloss eine Pflege, d.h. eine "statisch-konservative Zuwendung" (<ref-ruling> E. 3.6 S. 322 mit Hinweis).
2.4 2.4.1 Der Beschwerdegegner wurde infolge seiner Delinquenz bereits in den Jahren 1986, 1988, 1990, 1994 und 2002 begutachtet. Das aktuelle Gutachten vom 19. Mai 2008 berücksichtigt die damaligen Ergebnisse und die seither erfolgte Entwicklung. Der Beschwerdegegner weist gemäss diesem Gutachten eine kombinierte Persönlichkeitsstörung mit ängstlich unsicheren, neurotischen und narzisstischen Zügen (ICD 10 F 61.0) sowie eine Ersatzpädophilie auf. Mit moderater bis deutlicher Wahrscheinlichkeit müsse mit weiteren sexuellen Handlungen mit Mädchen bzw. sexueller Nötigung von Mädchen gerechnet werden. Es seien positive Entwicklungsschritte zu verzeichnen. Der Beschwerdegegner sei unter anderem konfliktfähiger geworden, weise eine bessere Kränkungstoleranz und ein gestärktes Selbstwertgefühl auf und zeige ansatzweise Opferempathie. Unverändert auffällig sei die fehlende Akzeptanz der pädosexuellen Persönlichkeitsanteile, die Verleugnung entsprechender Gewaltfantasien sowie Bagatellisierungs- und Verleugnungstendenzen (Gutachten S. 45). Es sei notwendig, eine weitere Verbesserung der Legalprognose anzustreben (Gutachten S. 41). In emotionalen und innerpsychischen Bereichen der Persönlichkeitsstörung müsse weiterhin mit kaum vorhersehbaren, situativen und stimmungsmässigen destabilisierenden Einflussfaktoren gerechnet werden, die insbesondere bei Veränderungen im Lebensalltag, bei Beziehungen mit Frauen, bei Problemen in der Familie und im Umfeld wirksam werden können (Gutachten S. 62). Nach insgesamt 20 Jahren Therapie, wovon knapp 10 Jahre in intensiver deliktorientierter Gruppen- und Einzeltherapie erfolgt seien, hätten die Persönlichkeitsstörung stabilisiert und die strukturelle Rückfallgefahr leicht vermindert werden können. Aus forensisch-psychiatrischer Sicht dürfe mit einer weiteren, eher geringen Beeinflussung der Persönlichkeitsmerkmale, sowie mit leichten, legalprognostisch relevanten Therapiefortschritten gerechnet werden. Eine Behebung der psychischen Störung und der strukturellen Rückfallgefahr könnten aber heute auch bei weiteren Therapieanstrengungen kaum erwartet werden (Gutachten S. 67). Von Seiten des Beschwerdegegners könne von einer guten Kooperation ausgegangen werden, die Therapien fortzusetzen. Eine stationäre Behandlung in der milieutherapeutischen Station für therapierbare Gewalt- und Sexualstraftäter der Strafanstalt D._, ergänzt durch eine Einzeltherapie, sei für die Bedürfnisse des Beschwerdegegners geeignet und erforderlich. Auch dem Sicherheitsaspekt müsse genügend Rechnung getragen werden. Inwiefern die Stabilisierung der Persönlichkeit und die in den letzten Jahren angeeigneten Selbstkontrollmöglichkeiten legalprognostisch Sicherheit gewährten, müsse in den nächsten 5 Jahren geprüft werden. (Gutachten S. 65 und 67 f.).
2.4.2 Dem Beschwerdegegner wird ein gewisser Therapieerfolg bescheinigt. Wurde die Prognose für die Begehung weiterer einschlägiger Straftaten im Gutachten vom 22. Februar 1994 noch als "sehr ungünstig" bezeichnet, so wies das Gutachten vom 23. August 2002 auf Veränderungen hin, die für eine Verringerung der Rückfallgefahr und eine Verbesserung der Legalprognose sprächen. Heute liegt das Rückfallrisiko noch bei "moderat bis deutlich". Insoweit kann auf die zutreffenden Ausführungen der Vorinstanz zu den verschiedenen Gutachten und Therapieberichten verwiesen werden (angefochtenes Urteil Ziff. V. S. 13 ff.).
Zwar hatte der Beschwerdegegner nach acht Jahren Therapie im Rahmen der ambulanten vollzugsbegleitenden Massnahme 1993 einen Rückfall, wobei er drei weitere Straftaten im Bereich sexueller Handlungen mit Kindern beging. Aufgrund dieses Rückfalls musste das Risiko im Gutachten von 1994 wieder höher eingeschätzt werden. Indessen wurde die intensive Gruppentherapie für Sexual- und Gewaltdelinquenten erst im Jahre 1997, also nach dem Rückfall, aufgenommen. Ab dem Jahr 2000 nahm der Beschwergegegner am Programm "AIP" teil, welches aus einer Kombination von Therapien (Gruppentherapiesitzungen, Sozialtraining und Einzeltherapie) besteht und ca. 7 bis 10 Stunden wöchentlich beansprucht. Das seit 10 Jahren angewendete Konzept zeigt grundsätzlich eine positive Veränderung risikorelevanter Persönlichkeitsmerkmale sowie deliktpräventive Fortschritte. Der Beschwerdegegner erhielt seit dem Jahr 2004 bzw. 2006 die Erlaubnis für begleitete Ausgänge und Urlaube. Dank der Therapie konnte er im Jahr 2004 eine Phase der Stagnation überwinden, sodass ihm im jährlichen Therapiebericht des Jahres 2005 wiederum eine vorsichtig positive Prognose für den weiteren Therapieverlauf gestellt wurde. In den Jahren 2006 und 2007 wurde ein erneuter Stillstand in der Entwicklung festgestellt.
2.4.3 Trotz des Therapiefortschrittes bestehen erhebliche Bedenken an einer Bewährung des Beschwerdegegners in Freiheit, da die Entwicklungsschritte der letzten zwanzig Jahre gemessen am Therapieziel bescheiden sind. Dies ergibt sich aus dem Therapiebericht vom 19. November 2007, worin sowohl die ordentliche Verwahrung als auch eine stationäre Massnahme als möglicher künftiger Rahmen für den Beschwerdegegner in Betracht gezogen werden. Das aktuelle Gutachten gelangt in groben Zügen zu denselben Ergebnissen wie dieser Therapiebericht. Dabei rechnet der Gutachter auch bei weiteren Therapieanstrengungen kaum mit einer Behebung der psychischen Störung und der strukturellen Rückfallgefahr (Gutachten S. 67 Ziff. 4). Trotz der bestehenden Unsicherheit über einen künftigen Therapieerfolg empfiehlt er die Fortsetzung weiterer therapeutischer Massnahmen nach <ref-law> in der Strafanstalt D._ auf der Station für therapierbare Gewalt- und Sexualstraftäter und die weitere Beobachtung der Entwicklung über einen Zeitraum von fünf Jahren.
2.4.4 Im vorliegenden Fall besteht aufgrund der ambivalenten gutachterlichen Ergebnisse ein gewisses Ermessen, ob die altrechtliche Verwahrung in eine stationäre Massnahme nach <ref-law> überführt oder die Verwahrung nach <ref-law> angeordnet wird. Einerseits spricht sich der Gutachter als qualifizierte Fachperson für eine weitere stationäre Behandlung des Beschwerdegegners aus. Andererseits weist er darauf hin, dass die Erwartungen an die künftige Entwicklung bescheiden sind. Die Vorinstanz ist den Empfehlungen des Gutachtens gefolgt und hat eine stationäre Massnahme in einer geschlossenen Einrichtung nach <ref-law> ausgesprochen.
Nach der bundesgerichtlichen Rechtsprechung liegt es im Ermessen des Sachrichters, in welchem Umfang er die verschiedenen Strafzumessungsfaktoren berücksichtigt. Es greift in Ermessensentscheide bei der Strafzumessung nur ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat (<ref-ruling> E. 2.1 S. 19 f. mit Hinweisen). Diese Rechtsprechung zur Strafzumessung lässt sich auf den Entscheid, welche Massnahme anzuordnen ist, weitgehend übertragen. In das von der Vorinstanz pflichtgemäss ausgeübte Ermessen ist mit Zurückhaltung einzugreifen. Dies gilt insbesondere dort, wo zwei Lösungen als vertretbar erscheinen und sich die Vorinstanz für eine dieser beiden entscheidet.
Auch wenn vom Beschwerdegegner lediglich kleine Fortschritte erwartet werden, so erscheint es gestützt auf die gutachterlichen Empfehlungen zumindest nicht ausgeschlossen, dass durch einen Therapeuten- und Therapiewechsel mehr Bewegung in die Entwicklung kommt und längerfristig eine deutliche Verringerung der Gefahr für künftige Straftaten nicht von vornherein ausgeschlossen werden kann (vgl. <ref-ruling> E. 3.4.2 S. 130 mit Hinweisen). Die Sicherheit für die Allgemeinheit kann dabei durch den Vollzug der Massnahme in einer geschlossenen Anstalt nach <ref-law> gewährt werden. In Anbetracht, dass eine Verwahrung die letzte mögliche Lösung, d.h. die "ultima ratio", darstellt, erweist sich deshalb die vorinstanzliche Anordnung einer stationären Massnahme in einer geschlossenen therapeutischen Einrichtung nach <ref-law> durch die Vorinstanz bundesrechtskonform.
Der weiterhin vom Beschwerdegegner ausgehenden Gefahr lässt sich dadurch begegnen, dass die Massnahme gegebenenfalls nach fünf Jahren verlängert wird und dass Vollzugslockerungen nur mit grösster Zurückhaltung unter straffer therapeutischer Begleitung gewährt werden. Stellt sich nach Ablauf von fünf Jahren bzw. nach einer weiteren Verlängerung der stationären Massnahme heraus, dass dieser definitiv kein Erfolg beschieden ist, so bleibt die Möglichkeit erhalten, eine Verwahrung anzuordnen, da der Beschwerdegegner eine Anlasstat im Sinne von <ref-law> begangen hat (<ref-ruling> E. 3.7 S. 324 mit Hinweis).
3. Die Beschwerde ist somit abzuweisen. Es sind keine Kosten zu erheben (<ref-law>). Dem Beschwerdegegner sind im Zusammenhang mit dem vorliegenden Beschwerdeverfahren keine Aufwendungen entstanden, er hat sich auch nicht aktiv daran beteiligt. Insoweit ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 21. Juli 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch