Sachverhalt: A. Der aus Pakistan stammende X._ (geb. 1972) reiste im November 1998 in die Schweiz ein und stellte erfolglos ein Asylgesuch. Nachdem die damalige Asylrekurskommission am 9. April 2002 seine Beschwerde abgewiesen hatte, heiratete er am 10. Juni desselben Jahres die aus Thailand stammende Schweizer Bürgerin Y._ (geb. 1957). Dadurch erhielt er eine bis zum 9. Juni 2003 befristete Aufenthaltsbewilligung für den Kanton Zürich. Mit Verfügung vom 25. August 2004 lehnte das Zürcher Migrationsamt eine Verlängerung der Bewilligung mit der Begründung ab, X._ berufe sich in rechtsmissbräuchlicher Weise auf eine nur noch formell bestehende Ehe. Diese Verfügung blieb unangefochten. Im Oktober 2004 verstarb Y._. Am 2. März 2005 ehelichte X._ die Schweizer Bürgerin Z._ (geb. 1980). Da diese von Zürich in den Kanton Luzern umgezogen war, stellte sie bei den Luzerner Behörden ein Gesuch um Erteilung einer Aufenthaltsbewilligung für X._. Am 4. September 2006 erklärte sie indes, sie ziehe das Gesuch zurück, da sie sich demnächst voneinander trennen würden. Im Oktober 2006 meldete sich X._ ohne seine Ehefrau wieder im Kanton Zürich und ersuchte dort um eine Aufenthaltsbewilligung, die ihm mit Befristung bis zum 1. März 2008 erteilt wurde. Sein Gesuch um Verlängerung der Bewilligung vom 11. Februar 2008 wies das Zürcher Migrationsamt am 16. Juni 2008 ab; die eheliche Gemeinschaft sei aufgegeben worden. Es setzte ihm gleichzeitig eine Frist zum Verlassen der Schweiz an. Die gegen diese Verfügung im Kanton erhobenen Rechtsmittel blieben erfolglos. B. X._ beantragt dem Bundesgericht mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 15. Juni 2009 den in dieser Sache kantonal zuletzt ergangenen Entscheid des Verwaltungsgerichts des Kantons Zürich vom 29. April 2009 aufzuheben. Die Sicherheitsdirektion des Kantons Zürich sei anzuweisen, ihm die Aufenthaltsbewilligung zu erteilen bzw. zu verlängern. Eventualiter sei die Sache zu neuem Entscheid an die Vorinstanz zurückzuweisen. C. Der Regierungsrat des Kantons Zürich - vertreten durch seine Staatskanzlei - und das Bundesamt für Migration ersuchen um Abweisung der Beschwerde. Das Verwaltungsgericht hat auf eine Vernehmlassung verzichtet, während sich die Sicherheitsdirektion des Kantons Zürich nicht geäussert hat. Mit von beiden Eheleuten unterzeichnetem Schreiben vom 29. Oktober 2009 bittet Z._, ihrem Gatten die Aufenthaltsbewilligung zu erteilen. D. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde mit Verfügung vom 18. Juni 2009 antragsgemäss die aufschiebende Wirkung hinsichtlich der Ausreiseverpflichtung zuerkannt.