Das Bundesgericht zieht in Erwägung:
1. A._ erhob am 21. November 2008 bei den Behörden des Kantons Zürich gegen X._ Strafantrag wegen Verletzung des Schriftgeheimnisses. Am 12. Februar 2009 stellte das Stadtrichteramt der Stadt Zürich das Verfahren gegen X._ ein.
Einen von A._ dagegen gerichteten Rekurs wies der Einzelrichter am Bezirksgericht Zürich mit Verfügung vom 16. Juni 2009 ab, soweit darauf einzutreten war. X._ wurde keine Entschädigung ausgerichtet, weil er seine Stellungnahme am 8. Juni 2009 verspätet eingereicht habe.
X._ führt beim Bundesgericht Beschwerde in Strafsachen und beantragt, die Verfügung vom 16. Juni 2009 sei aufzuheben. Die Sache sei zur Neubeurteilung an den Einzelrichter zurückzuweisen, soweit er durch die Verfügung beschwert sei.
Der Einzelrichter hat auf eine Vernehmlassung verzichtet. Der Beschwerdegegner ist unbekannten Aufenthaltes. Gemäss Bekanntmachung im Bundesblatt vom 27. Oktober 2009 wurde ihm eine Frist von 20 Tagen ab der Publikation angesetzt, um zur Beschwerde Gegenbemerkungen einzureichen. Die Frist verstrich ungenützt.
2. Der Beschwerdeführer rügt, die Vorinstanz habe seinen Anspruch auf rechtliches Gehör verletzt (Beschwerde S. 2 Ziff. I/2). Obschon seine Eingabe vom 8. Juni 2009 entgegen der Annahme der Vorinstanz rechtzeitig eingereicht worden sei, sei sie insbesondere bei der Frage, ob ihm erhebliche Aufwendungen entstanden seien und ihm deshalb eine Prozessentschädigung zuzusprechen sei, nicht berücksichtigt worden (Beschwerde S. 3 Ziff. II/1, S. 4 Ziff. IV/1).
Die Rüge ist begründet. Dem Beschwerdeführer wurde eine letzte Frist bis 6. Juni 2009 angesetzt, um zum Rekurs des Beschwerdegegners Stellung zu nehmen (KA act. 12). Der 6. Juni 2009 war ein Samstag. Ist der letzte Tag einer Frist ein Samstag, endigt sie am nächsten Werktag (§ 192 des Gerichtsverfassungsgesetzes des Kantons Zürich). Folglich endigte die Frist am Montag, den 8. Juni 2009. An diesem Tag hat der Beschwerdeführer seine Stellungnahme auf der Post aufgegeben (KA act. 15). Entgegen der Annahme der Vorinstanz erfolgte die Stellungnahme fristgerecht.
Der Beschwerdeführer beantragt eine Neubeurteilung der Sache durch die Vorinstanz, soweit er durch die angefochtene Verfügung beschwert sei. Beschwert ist er insoweit, als die Vorinstanz zum Schluss kommt, die Stellungnahme sei verspätet und deshalb auch hinsichtlich der Frage einer allfälligen Entschädigung unbeachtlich (angefochtener Entscheid S. 11 E. V und Dispositiv Ziff. 4). Diese Annahme ist offensichtlich unrichtig und deshalb willkürlich.
3. Da der Beschwerdegegner keine Anträge gestellt hat, sind keine Gerichtskosten zu erheben.
Eine Parteientschädigung ist auszurichten, wenn ein in eigener Sache handelnder Beschwerdeführer geltend macht, es seien ihm Kosten durch den Rechtsstreit verursacht worden (Art. 1 des Reglements des Bundesgerichts über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht vom 31. März 2006). Der Beschwerdeführer verlangt eine Entschädigung. Er ist Rechtsanwalt und macht geltend, es seien ihm erhebliche Aufwendungen entstanden (Beschwerde S. 3 Ziff. II/3). Folglich hat ihn der Kanton Zürich für das bundesgerichtliche Verfahren zu entschädigen.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, die Verfügung des Bezirksgerichts Zürich, Einzelrichteramt für Zivil- und Strafsachen, vom 16. Juni 2009 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird dem Beschwerdeführer, A._ durch Publikation im Bundesblatt, dem Stadtrichteramt Zürich und dem Bezirksgericht Zürich, Einzelrichteramt für Zivil- und Strafsachen, schriftlich mitgeteilt.
Lausanne, 21. Dezember 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Monn