Sachverhalt:
A. Der stellvertretende Leitende Staatsanwalt der Staatsanwaltschaft III des Kantons Zürich, Andreas Ochsenbein, führt gegen X._ eine Strafuntersuchung wegen Betrugs und weiterer Delikte sowie ein Rechtshilfeverfahren zugunsten der Staatsanwaltschaft Potsdam (D). Beide Verfahren betreffen im Wesentlichen denselben Sachverhalt.
Am 7. November 2008 erhob X._ Aufsichtsbeschwerde gegen die Staatsanwaltschaft III. Die Oberstaatsanwaltschaft nahm die Eingabe als Aufsichtsbeschwerde gegen die Staatsanwaltschaft III sowie als Ablehnungsbegehren gegen Staatsanwalt Ochsenbein entgegen. Mit Verfügung vom 15. Januar 2009 gab sie Ersterer keine Folge und wies Letztere kostenfällig ab. Eine Kopie der Beschwerdeschrift vom 7. November 2008 überwies sie zudem als Strafanzeige gegen Staatsanwalt Ochsenbein der dafür zuständigen Staatsanwaltschaft I.
X._ rekurrierte gegen die Abweisung des Ablehnungsbegehrens und die Kostenauflage an die Direktion des Innern und der Justiz des Kantons Zürich. Diese wies den Rekurs am 20. Mai 2009 ab und auferlegte ihm die Kosten des Rekursverfahrens.
B. Mit Beschwerde in Strafsachen beantragt X._, diese Verfügung der Direktion des Innern und der Justiz aufzuheben, Staatsanwalt Ochsenbein umgehend vom Straf- und vom Rechtshilfeverfahren abzuziehen oder die Sache eventuell mit den entsprechenden Auflagen an die Vorinstanz zurückzuweisen und alle Verfahrenshandlungen ab dem 7. November 2008, an denen Staatsanwalt Ochsenbein beteiligt war, aufzuheben oder die Sache eventuell mit den entsprechenden Auflagen an die Vorinstanz zurückzuweisen.
C. Die Oberstaatsanwaltschaft und die Direktion des Innern und der Justiz verzichten auf Vernehmlassung. Staatsanwalt Ochsenbein bean-tragt, die Beschwerde abzuweisen.
In seiner Replik stellt X._ fest, es seien dem Bundesgericht nur einige wenige Verfahrensakten eingereicht worden, er gehe davon aus, dass das Bundesgericht alle für die Beurteilung der Beschwerde erforderlichen Akten einholen werde. Im Übrigen verweise er auf seine Beschwerde.
Staatsanwalt Ochsenbein teilt mit, dass in dieser Sache gegen ihn eine Strafuntersuchung wegen Amtsgeheimnisverletzung eingeleitet worden sei.

Erwägungen:
1. Der angefochtene Entscheid schliesst weder das Straf- noch das Rechtshilfeverfahren gegen den Beschwerdeführer ab, er ermöglicht vielmehr deren Weiterführung. Es handelt sich um einen selbständig eröffneten, kantonal letztinstanzlichen Zwischenentscheid über ein Ablehnungsbegehren, gegen den die Beschwerde in Strafsachen nach <ref-law> zulässig ist. Sie richtet sich einerseits gegen die Beteiligung des Staatsanwaltes an einem Strafverfahren, anderseits an einem Rechtshilfeverfahren in Strafsachen. Die Beschwerdefrist für die Anfechtung von Entscheiden beträgt im ersten Fall dreissig, im zweiten Fall zehn Tage (Art. 100 Abs. 1 und Abs. 2 lit. b BGG). Der Beschwerdeführer erhielt die angefochtene Verfügung am 26. Mai 2009 zugestellt und erhob am 26. Juni 2009 Beschwerde in Strafsachen. Sie ist damit rechtzeitig erfolgt, soweit sie sich gegen die Beteiligung des Staatsanwaltes am Strafverfahren richtet. Soweit sie das Rechtshilfeverfahren betrifft, ist sie indessen offensichtlich verspätet, weshalb sich eine Überweisung an das nach Art. 28 Abs. 1 lit. e des Strafgerichtsgesetzes für ihre Beurteilung zuständige Bundesstrafgericht erübrigt.
Die Direktion des Innern und der Justiz ist kein oberes kantonales Gericht im Sinne von <ref-law>. Das ändert an der Zulässigkeit der Beschwerde gegen die Mitwirkung des Staatsanwaltes indessen nichts, da die Kantone bis zum noch nicht erfolgten Inkrafttreten der schweizerischen Strafprozessordnung Zeit haben, ihre Gerichtsorganisation den Anforderungen dieser Bestimmung anzupassen (<ref-law>). Als Beschuldigter ist der Beschwerdeführer zur Beschwerde berechtigt (Art. 81 Abs. 1 lit. a und b BGG). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, weshalb auf die Beschwerde gegen die Mitwirkung des Staatsanwaltes am Strafverfahren einzutreten ist.
Die dem Bundesgericht eingereichten Akten sind für die Beurteilung der vorliegenden Beschwerde ausreichend, der Beizug der gesamten Akten des Straf- und des Rechtshilfeverfahrens erübrigt sich.
2. Gemäss § 96 Ziff. 4 des Zürcher Gerichtsverfassungsgesetzes vom 13. Juni 1976 (GVG) kann ein Staatsanwalt abgelehnt werden, wenn Umstände vorliegen, die ihn befangen erscheinen lassen.
Nach <ref-law> kann ein Staatsanwalt abgelehnt werden, wenn Umstände vorliegen, die nach objektiven Gesichtspunkten geeignet sind, den Anschein der Befangenheit zu erwecken (<ref-ruling> E. 2b S. 198 f. mit Hinweisen). Dabei gilt es aber dem spezifischen Umfeld und Aufgabenbereich der betroffenen Behörde Rechnung zu tragen. Fungiert er wie hier als Untersuchungsrichter, sind Sachlichkeit, Unbefangenheit und Objektivität namentlich insofern zu erwarten, als er sich vor Abschluss der Untersuchung grundsätzlich nicht darauf festlegen soll, dass der angeschuldigten Person ein strafbares Verhalten zur Last zu legen sei. Auch hat er den entlastenden Indizien und Beweismitteln ebenso Rechnung zu tragen wie den belastenden (Urteile 1P.109/2005 vom 4. Mai 2005 E. 2.1.1; 1P.709/2005 vom 21. Februar 2006 E. 3.1; je mit Hinweisen). Es kann indessen vorkommen, dass sich die Untersuchungsbehörden in Erfüllung ihrer Aufgaben bereits vor Abschluss des Verfahrens in tatsächlicher oder rechtlicher Hinsicht zum Gegenstand der Untersuchung zu äussern haben; dabei kommen sie nicht umhin, die aufgrund des jeweiligen Verfahrensstands vorläufig gebildete Meinung offenzulegen. Diesfalls kann und muss vorausgesetzt werden, dass der Untersuchungsrichter in der Lage ist, seine Beurteilung des Prozessstoffs entsprechend dem jeweils neuesten Stand des Verfahrens ständig neu zu überprüfen und allenfalls zu revidieren. Unter diesen Umständen vermag eine auf den aktuellen Verfahrensstand abgestützte vorläufige Beurteilung und Bewertung keine Vorverurteilung oder Befangenheit zu begründen (vgl. <ref-ruling> E. 2d S. 200; Urteil des Bundesgerichts 1B_155/2008 vom 13. November 2008 E. 2.5).
Zu prüfen ist im Folgenden, ob die vom Beschwerdeführer vorgebrachten Umstände den Staatsanwalt befangen erscheinen lassen. Diesfalls verstiesse der angefochtene Entscheid gegen <ref-law>. Der ebenfalls vorgebrachten Rüge, die Vorinstanz habe mit der Abweisung des Ablehnungsbegehrens § 96 GVG willkürlich angewandt, kommt keine selbständige Bedeutung zu.
3. 3.1 Der Beschwerdeführer macht geltend, der Staatsanwalt habe im Fax an die Staatsanwaltschaft Potsdam vom 30. Juli 2007 Aussagen von "eindeutig negativer Konnotation" gemacht (Beschwerde Ziff. 9 S. 4 f.). Insbesondere habe er die Verteidigung als "aggressiv" bezeichnet, dem Beschwerdeführer vorgeworfen, zu einer Einigung nicht bereit gewesen zu sein und spekuliert, er würde die von ihm zu erlassende Verfügung gewiss anfechten. Die Vorinstanz habe diese Aussagen im angefochtenen Entscheid als "eher unüblich" und "objektiv betrachtet auch nicht erforderlich" bezeichnet, jedoch den unzutreffenden Schluss gezogen, sie seien nicht geeignet, den Staatsanwalt befangen erscheinen zu lassen.
Mit dem Ausdruck "aggressive Verteidigung" wird indessen keineswegs eine eindeutig negative Vorstellung assoziiert. Er kann zwar einen negativen Beigeschmack erwecken, etwa in dem Sinne, dass dem Beschuldigten mit einer eher kooperativen Verteidigungsstrategie besser gedient wäre als mit einer strikt konfrontativen. Dies muss indessen nicht sein, mit "aggressiv" wird in der Regel eine Verteidigung bezeichnet, die man als forsch und kompromisslos einstuft, die jederzeit bereit ist, dem Untersuchungsrichter oder Ankläger unerschrocken Paroli zu bieten und alles unternimmt, was dem Mandanten zum Vorteil gereichen könnte. Der Staatsanwalt erscheint somit keineswegs als befangen, weil er die Verteidigung des Beschwerdeführers als aggressiv bezeichnete, ganz abgesehen davon, dass dieser gar nicht geltend macht, diese Beurteilung sei unzutreffend.
3.2 Der Beschwerdeführer bringt vor (Beschwerde Ziff. 10 S. 5 f.), der Staatsanwalt habe einen krassen Verfahrensfehler begangen, indem er den Entwurf der 1. Teil-Schlussverfügung der Staatsanwaltschaft Potsdam zugestellt habe. Dieses Vorgehen sei widerrechtlich.
Diesen Vorwurf begründet der Beschwerdeführer indessen allein mit Verweisen auf seine Rekursschrift im kantonalen Verfahren. Das ist im Verfahren vor Bundesgericht nicht zulässig (<ref-law>; <ref-ruling> E. 3.2 S. 400), weshalb darauf nicht einzutreten ist.
3.3 Der Beschwerdeführer hält den Staatsanwalt für befangen, weil dieser ihm zu Unrecht unterstellt habe, gegen Mitarbeiter der Staatsanwaltschaft Strafanzeige erhoben zu haben (Beschwerde Ziff. 11 S. 6 f.).
Nach der unbestrittenen Darstellung im angefochtenen Entscheid (S. 3 2. Absatz) erkundigte sich der Beschwerdeführer sowohl beim Staatsanwalt als auch beim Obergericht danach, ob gegen den Vorgänger des Staatsanwaltes und dessen Mitarbeiterin eine Strafuntersuchung eröffnet worden sei und verlangte für den Fall einer negativen Antwort eine Begründung. Er stellte sich dabei auf den Standpunkt, es stehe fest, dass die beiden das Amtsgeheimnis verletzt hätten.
Der Beschwerdeführer hat somit bei einer Strafverfolgungsbehörde und einem mit Strafsachen befassten Gericht ein strafrechtlich relevantes Verhalten namentlich bekannter Personen behauptet, sich nach der Eröffnung bzw. dem Gang des Strafverfahrens erkundigt und für den Fall, das ein solches nicht eingeleitet wurde, eine Begründung bzw. Rechtfertigung verlangt. Im Kanton Zürich sind Behörden und Beamte, was ihm als Zürcher Rechtsanwalt bewusst sein muss, verpflichtet, strafbare Handlungen, die ihnen bei der Ausübung ihrer Amtstätigkeit zur Kenntnis gelangen, anzuzeigen (§ 21 der Strafprozessordnung des Kantons Zürich vom 4. Mai 1919). Der Beschwerdeführer hat somit alles Erforderliche vorgekehrt, um die Eröffnung einer Strafuntersuchung gegen den Vorgänger des Staatsanwaltes und dessen Mitarbeiterin zu bewirken. Insofern ist die Äusserung des Staatsanwaltes, der Beschwerdeführer habe eine (förmliche) Strafanzeige eingereicht, allenfalls ungenau. Faktisch hat dieser deren Verfolgung verlangt, die Aussage des Staatsanwaltes trifft in der Sache zu und ist daher jedenfalls nicht geeignet, ihn befangen erscheinen zu lassen.
3.4 In seiner Aufsichtsbeschwerde vom 7. November 2008 an die Oberstaatsanwaltschaft hat der Beschwerdeführer dem Staatsanwalt u.a. vorgeworfen, er habe der Staatsanwaltschaft Potsdam widerrechtlich Akten und Informationen, namentlich den Entwurf der 1. Teil-Schlussverfügung, zukommen lassen. Er machte zusammenfassend geltend, weder der Staatsanwalt noch dessen Vorgänger seien gewillt oder in der Lage gewesen, rechtsstaatlich korrekte Verfahren gegen ihn zu führen. Es dränge sich angesichts der festgestellten Gesetzesverstösse die Frage auf, ob es sich dabei nur um die Spitze des Eisbergs handle und nicht weitere, bisher unbekannt gebliebene Unregelmässigkeiten vorgekommen seien. Die Eingabe schliesst ab mit der Mutmassung, dass sich der Staatsanwalt einer Amtsgeheimnisverletzung schuldig gemacht haben dürfte.
In seiner Vernehmlassung an die Oberstaatsanwaltschaft vom 27. November 2008 führte der Staatsanwalt aus, er sei davon ausgegangen, die Oberstaatsanwaltschaft hätte sofort (d.h. ohne Einholung einer Vernehmlassung) entscheiden können, auf das "angezeigte Wahnde-likt" nicht einzutreten. Mit dieser Formulierung bringt er klarerweise zum Ausdruck, dass er den Vorwurf, er habe bei seinem Verkehr mit der deutschen Staatsanwaltschaft den Straftatbestand der Amtsgeheimnisverletzung erfüllt, für offensichtlich unzutreffend hält. Die Formulierung mag zwar etwas salopp erscheinen, lässt aber nicht ohne Weiteres auf eine Befangenheit des Staatsanwaltes schliessen. Wer wie der Beschwerdeführer harte und auch überzogene, nur teilweise mit sachlichen Argumenten untermauerte Kritik äussert und dem Staatsanwalt pauschal die Fähigkeit und den Willen abspricht, die Verfahren gegen ihn in einer recht- und gesetzmässigen Weise zu führen, hat keinen Anlass, jede Formulierung der kritisierten Gegenseite auf die Goldwaage zu legen. Er muss sich vielmehr bis zu einem gewissen Grad gefallen lassen, dass auch diese nicht emotionsfrei reagiert und etwas Mühe bekundet, Gelassenheit zu bewahren.
3.5 In der erwähnten Vernehmlassung vom 27. November 2008 führte der Staatsanwalt aus, dem Beschwerdeführer gehe es mit seiner Aufsichtsbeschwerde darum, das Strafverfahren gegen ihn weiter zu verzögern. Für den Beschwerdeführer zeigt dies dessen Befangenheit (Beschwerde Ziff. 14 S. 8 f.).
Der Staatsanwalt legte in der Vernehmlassung dar, dass er die vom Beschwerdeführer erhobene Kritik an seiner Amtsführung ebenso wie den Vorwurf, das Amtsgeheimnis verletzt zu haben, für offensichtlich unbegründet hält. Bei dieser aus seiner Sicht jedenfalls vertretbaren Auffassung liegt die Folgerung nahe, dass es dem Beschwerdeführer mit seiner Aufsichtsbeschwerde darum ging, das Verfahren zu verzögern. Die entsprechende Mutmassung des Staatsanwaltes im Verlaufe des vor allem auch von Seiten der Verteidigung mit harten Bandagen geführten Verfahrens (oben E. 3.4) ist nicht geeignet, ihn befangen erscheinen zu lassen.
3.6 Der Beschwerdeführer hat in der Beilage zu einem Schreiben an den Staatsanwalt vom 24. September 2007 die Akten zum Themenkreis "Narcisse" als für das Strafverfahren unerheblich bezeichnet. Der Staatsanwalt ist anderer Auffassung und hat dem Beschwerdeführer in einer Eingabe ans Bundesstrafgericht vorgeworfen, diesbezüglich "falsche Angaben" gemacht zu haben. Dieser sieht sich dadurch als Lügner denunziert und vorverurteilt.
Mit dem Vorwurf, "falsche Angaben" gemacht zu haben, bringt der Staatsanwalt zum Ausdruck, die Auffassung des Bescherdeführers, wonach die Akten zum Thema "Narcisse" für das Strafverfahren unerheblich seien, treffe nicht zu. Auch wenn der Ausdruck "falsche Angaben" normalerweise für unwahre Tatsachenbehauptungen verwendet wird und in diesem Zusammenhang missverständlich ist, kann doch kein ernsthafter Zweifel daran aufkommen, dass der Staatsanwalt den Beschwerdeführer nicht einer wissentlich unwahren Sachdarstellung bezichtigte, sondern einer unzutreffenden Beurteilung der Massgeblichkeit der "Narcisse"-Akten für das Strafverfahren. Er hat ihn damit nicht als Lügner vorverurteilt.
3.7 Zusammenfassend ist festzuhalten, dass die Vorwürfe des Beschwerdeführers weder für sich allein noch bei gesamthafter Betrachtung geeignet sind, den Staatsanwalt befangen erscheinen zu lassen.
4. Die Beschwerde ist somit abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Stv. Leitenden Staatsanwalt sowie der Oberstaatsanwaltschaft und der Direktion der Justiz und des Innern des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 13. Oktober 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Störi