Sachverhalt: A. Das Bezirksgericht Zürich sprach X._ am 22. April 2004 des mehrfachen bandenmässigen Diebstahls und weiterer Delikte schuldig und wies ihn gestützt auf Art. 100bis aStGB in eine Arbeitserziehungsanstalt ein. Nach seiner bedingten Entlassung aus dem Massnahmenvollzug wurde er während der Probezeit erneut straffällig. Das Bezirksgericht Zürich verurteilte ihn am 24. Januar 2008 wegen gewerbsmässigen Betrugs und weiterer Delikte zu 18 Monaten Freiheitsstrafe und versetzte ihn in den Vollzug der Massnahme nach Art. 61 StGB zurück. Das Amt für Justizvollzug des Kantons Zürich versetzte X._ am 18. März 2008 aus der Massnahme in Sicherheitshaft. Am 14. Mai 2008 hob es die Massnahme auf und beantragte dem Bezirksgericht Zürich, betreffend die Verurteilung vom 22. April 2004 eine Strafe auszufällen und zu prüfen, ob diverse Freiheitsstrafen zu vollziehen seien bzw. ob in Bezug auf die Reststrafe die Voraussetzungen der bedingten Entlassung oder der bedingten Freiheitsstrafe vorlägen. Das Bezirksgericht Zürich hob am 10. Juli 2008 die vom Bezirksgericht Zürich am 22. April 2004 gegen X._ angeordnete stationäre Massnahme auf, in welche er mit Urteil des Bezirksgerichts Zürich vom 24. Januar 2008 zurückversetzt worden war. Anstelle der aufgehobenen Massnahme verhängte es eine Freiheitsstrafe von drei Jahren, als Zusatzstrafe zur Freiheitsstrafe von 18 Monaten, zu welcher er am 24. Januar 2008 verurteilt worden war. Es ordnete an, diese beiden Strafen, sowie 6 weitere Haft- und Gefängnisstrafen von insgesamt 73 Tagen Dauer, seien zu vollziehen und rechnete daran 1378 Tage erstandenen Freiheitsentzug an. Es ordnete den Vollzug der Reststrafe an und verweigerte eine bedingte Entlassung. Es auferlegte X._ die Verfahrenskosten, inklusive der Kosten für die amtliche Verteidigung, nahm sie jedoch einstweilen auf die Gerichtskasse. Mit bezirksgerichtlicher Präsidialverfügung vom 18. August 2008 wurde X._ der vorzeitige Strafantritt bewilligt, unter Aufrechterhaltung der Sicherheitshaft. Mit Verfügung vom 23. September 2008 entliess der Präsident der III. Strafkammer des Obergerichts X._ wegen drohender Überhaft aus der Sicherheitshaft. Die Entlassung erfolgte am 25. September 2008. Am 19. Februar 2009 hiess das Obergericht des Kantons Zürich den Rekurs von X._ gegen den Beschluss des Bezirksgerichts vom 10. Juli 2008 teilweise gut. Es nahm davon Vormerk, dass vier Haftstrafen von insgesamt 51 Tagen Dauer verjährt waren und änderte die Kostenregelung. Es auferlegte ihm die Kosten der amtlichen Verteidigung mit der Bestimmung, dass er sie erst bezahlen müsse, wenn er dazu in der Lage sein werde. Im Übrigen wies es den Rekurs ab. Die Kosten des Rekursverfahrens (ohne amtliche Verteidigung) auferlegte es X._ zu 7/8, die Kosten für die amtliche Verteidigung im Rekursverfahren ebenfalls zu 7/8, mit der Bestimmung, er müsse sie erst begleichen, wenn er dazu in der Lage sei. B. Mit Beschwerde in Strafsachen beantragt X._, diesen Beschluss des Obergerichts aufzuheben und die Sache zur Beurteilung der Frage der bedingten Entlassung aus dem Strafvollzug an die Vorinstanz zurückzuweisen. Ausserdem ersucht er um unentgeltliche Rechtspflege und Verbeiständung. C. Das Obergericht und die Oberstaatsanwaltschaft verzichten auf Vernehmlassung. 