Sachverhalt:
A. Die Staatsanwaltschaft Zürich-Sihl auferlegte X._ am 20. April 2007 wegen Widerhandlung gegen das Betäubungsmittelgesetz (Art. 19 Ziff. 1 Abs. 4 und 5) eine Geldstrafe von 30 Tagessätzen zu Fr. 30.--, wovon 24 Tagessätze durch Haft erstanden sind, und eine Busse von Fr. 300.--. Sie schob den Vollzug der Geldstrafe bei einer Probezeit von 2 Jahren bedingt auf.
Gestützt auf einen rechtskräftigen Wegweisungsentscheid wurde X._ am 2. April 1998 und letztmals am 1. Mai 2007 aufgefordert, das Land unverzüglich zu verlassen. Dieser Aufforderung leistete er keine Folge.
B. Mit Strafbefehl vom 14. Juni 2007 erkannte die Staatsanwaltschaft Zürich-Sihl X._ schuldig der Widerhandlung gegen Art. 23 Abs. 1 al. 4 des Bundesgesetzes über Aufenthalt und Niederlassung der Ausländer (ANAG). Sie widerrief den bedingten Vollzug der erwähnten Geldstrafe und belegte ihn mit einer Gesamtstrafe von 30 Tagen Freiheitsstrafe.
Nach Ablauf der 10-tägigen Frist erhob X._ Einsprache und ersuchte unter anderem um Wiederherstellung der Einsprachefrist. Der Einzelrichter in Strafsachen des Bezirkes Zürich wies das Gesuch am 20. August 2007 ab. Den Rekurs ans Obergericht des Kantons Zürich wies dieses am 25. Oktober 2007 ab, soweit es darauf eintrat.
C. X._ führt Beschwerde in Strafsachen und beantragt, das angefochtene Urteil sei aufzuheben, und er sei mit einer milden Geldstrafe zu bestrafen. Eventualiter sei die Frist zur Einsprache gegen den Strafbefehl vom 14. Juni 2007 wiederherzustellen und die Sache an die Vorinstanz zurückzuweisen.
Das Obergericht beantragt in seiner Vernehmlassung sinngemäss, die Beschwerde sei abzuweisen (act. 10). Die Oberstaatsanwaltschaft des Kantons Zürich hat auf eine Vernehmlassung verzichtet (act. 11).

Erwägungen:
1. Gemäss § 199 Abs. 1 GVG/ZH kann das Gericht auf Antrag der säumigen Partei eine Frist wiederherstellen und eine Verhandlung neu ansetzen.
1.1 Eine Wiederherstellung ist nur möglich, wenn eine Frist wider den Willen der Partei verpasst wurde. Ob die Partei die Frist absichtlich verstreichen liess, hängt davon ab, ob ihre Willensbildung fehlerfrei zu Stande gekommen ist. Wurde sie von ihrem Anwalt über die Aussichten eines Rechtsmittels falsch beraten und befand sie sich demzufolge hinsichtlich der Aussichten eines Rechtsmittels in einem wesentlichen Irrtum, der sie zum Verzicht auf das Rechtsmittel veranlasste, so muss ihr die Möglichkeit der Wiederherstellung offen stehen; denn es wäre mit dem Ziel der materiellen Gerechtigkeit unverträglich, die Partei einen derartigen Fehler ihres Anwalts entgelten zu lassen (ZR 86 Nr. 90 E. 3).
1.2 Nachdem der Beschwerdeführer den Strafbefehl vom 14. Juni 2007 erhalten hatte, suchte er die offene Rechtsberatung der "Rechtsauskunft Anwaltskollektiv" auf. Dort riet ihm ein Rechtsanwalt - nachdem dieser Rücksprache mit der Staatsanwaltschaft Zürich-Sihl genommen hatte - davon ab, gegen den Strafbefehl Einsprache zu erheben.
Nach Ablauf der Einsprachefrist konsultierte der Beschwerdeführer seinen jetzigen Rechtsvertreter, der die Erfolgsaussichten des Rechtsmittels positiv einschätzte, weil es an einer gesetzlichen Grundlage für die Ausfällung einer Freiheitsstrafe fehle. Dementsprechend focht er den Entscheid nachträglich an und ersuchte um Wiederherstellung der Einsprachefrist.
1.3 Die Vorinstanz begründet die Anwendbarkeit von <ref-law> auf das ANAG wie folgt:
Weil das ANAG an die Revision des Allgemeinen Teils des Strafgesetzbuches angepasst worden sei, sei dieser grundsätzlich nicht anwendbar. Eine Ausnahme bilde allerdings <ref-law>, welcher unter anderem einen ausdrücklichen Vorbehalt der Anwendbarkeit von <ref-law> statuiere. Damit werde die rechtliche Grundlage für die Anwendbarkeit von <ref-law> auch für jene Bundesgesetze begründet, deren Strafnormen an die revidierten allgemeinen Bestimmungen des StGB angepasst wurden und für die der Allgemeine Teil des StGB somit grundsätzlich nicht gelte. Die Botschaft führe dazu aus, dass dieser Vorbehalt gewährleisten solle, "dass im Nebenstrafrecht die Strafrahmen grundsätzlich nicht geändert und nur die Strafarten angepasst werden". <ref-law> sei folglich auch auf das ANAG anwendbar (angefochtener Entscheid S. 7 Ziff. 5.3).
1.4 Der Beschwerdeführer verweist zu Recht auf weitere Erläuterungen der Botschaft:
"Es wäre - und sei es auch nur für eine Übergangszeit - viel zu umständlich, wenn bei der Anwendung dieser Gesetze (aus dem Zusammenhang ergibt sich, dass folgende Gesetze gemeint sind: SVG, ANAG und BetmG) immerzu ein Umrechnungsschlüssel aus dem StGB herangezogen werden müsste. Deshalb soll in diesen Erlassen von herausragender praktischer Bedeutung die wirklich verhängbare Strafe schon selber angedroht werden. Eine Anpassung dieser Nebenstrafrechtserlasse soll deshalb im Rahmen der vorliegenden AT-Revision vorgenommen werden.
"Es wäre - und sei es auch nur für eine Übergangszeit - viel zu umständlich, wenn bei der Anwendung dieser Gesetze (aus dem Zusammenhang ergibt sich, dass folgende Gesetze gemeint sind: SVG, ANAG und BetmG) immerzu ein Umrechnungsschlüssel aus dem StGB herangezogen werden müsste. Deshalb soll in diesen Erlassen von herausragender praktischer Bedeutung die wirklich verhängbare Strafe schon selber angedroht werden. Eine Anpassung dieser Nebenstrafrechtserlasse soll deshalb im Rahmen der vorliegenden AT-Revision vorgenommen werden.
...
Für die Strafdrohungen derjenigen Erlasse, die nicht im Rahmen der vorliegenden Revision angepasst werden, soll in Artikel 333 Absätze 3-5 E ein Umrechnungsschlüssel vorgesehen werden. ...
... Die allgemeinen Bestimmungen des StGB finden ausnahmsweise keine Anwendung dann, wenn ein Nebenstrafrechtserlass eigene einschlägige Vorschriften aufstellt. Diese Ausnahme gilt auch bei der Transformation der Strafdrohungen des Nebenstrafrechts" (Botschaft zur Änderung des Schweizerischen Strafgesetzbuches ... vom 21. September 1998, S. 2153 f.).
Diese Ausführungen unterscheiden klar zwischen SVG, ANAG und BetmG einerseits, die parallel zur Revision des Allgemeinen Teils des Strafgesetzbuches angepasst werden sollen, und den übrigen Nebenstrafrechtserlassen anderseits, für welche in Art. 333 Abs. 3-5 StGB Umrechnungsschlüssel vorgesehen sind. Dass Abs. 4 letzterer Bestimmung auch auf SVG, ANAG und BetmG anwendbar sein soll, geht aus der Botschaft nicht hervor. Vielmehr wird dort ausdrücklich festgehalten, dass die allgemeinen Bestimmungen des Strafgesetzbuches nicht anwendbar sind, wenn ein Erlass eigene Normen aufstellt, und zwar auch solche hinsichtlich der Transformation.
1.5 Der Beschwerdeführer hielt sich vom 2. April 1998 bis 13. Juni 2007 rechtswidrig in der Schweiz auf.
Bis Ende 2006 drohte das Ausländerstrafrecht bei illegalem Aufenthalt eine Freiheitsstrafe von maximal sechs Monaten an (Art. 23 Abs. 1 ANAG in der Fassung gemäss BG vom 8. Oktober 1948, AS 1949 I 225). Diese Strafe wurde bei der Einführung des neuen Allgemeinen Teils des Strafgesetzbuches am 1. Januar 2007 durch 180 Tagessätze Geldstrafe ersetzt (AS 2006, 3536). Diese Strafandrohung ist milder als die frühere und daher auch auf das rechtswidrige Verweilen vor dem 1. Januar 2007 anwendbar (<ref-law>).
Soweit der Beschwerdeführer für das ausländerrechtliche Delikt mit Freiheitsstrafe belegt wurde, fehlt es an einer expliziten Gesetzesgrundlage in Art. 23 Abs. 1 ANAG (in der Fassung des BG vom 13. Dezember 2002, AS 2006, 3459, 3536), weshalb der angefochtene Entscheid gegen Bundesrecht (Art. 1 und <ref-law>) verstösst (<ref-ruling> E. 8.4).
1.6 Indem die kantonalen Gerichte im Fall des Beschwerdeführers von einer falschen Rechtsauffassung bezüglich der Anwendbarkeit von <ref-law> ausgingen, verweigerten sie ihm willkürlich die Wiederherstellung der Einsprachefrist (§ 199 Abs. 1 GVG/ZH). Deshalb ist seinem diesbezüglichen Antrag stattzugeben und die Sache an die Vorinstanz zurückzuweisen (<ref-law>).
1.7 Bei diesem Ausgang des Verfahrens erübrigen sich Ausführungen zur amtlichen Verteidigung des Beschwerdeführers (Beschwerdeschrift S. 5 f. Ziff. 2.2; angefochtener Entscheid S. 5 Ziff. 4).
2. Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege. Da er obsiegt, ist sein Gesuch gegenstandslos. Sein Rechtsvertreter ist vom Kanton Zürich angemessen zu entschädigen. Eine Gerichtsgebühr entfällt (Art. 68 Abs. 1 und Art. 66 Abs. 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, die Einsprachefrist gegen den Strafbefehl der Staatsanwaltschaft Zürich-Sihl vom 14. Juni 2007 wiederhergestellt und die Sache zur Neubeurteilung an die Vorinstanz zurückgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird als gegenstandslos abgeschrieben.
3. Es werden keine Kosten erhoben.
4. Der Kanton Zürich hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. Juni 2008
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Schneider Borner