Sachverhalt: A. Der aus dem Kosovo stammende X._ (geb. 1971) heiratete am 23. März 1995 in seinem Heimatland eine in der Schweiz niedergelassene (inzwischen hier eingebürgerte) Mazedonierin. Am 14. Juni 1995 reiste er in die Schweiz ein, wo ihm eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau erteilt wurde. Am 17. Oktober 2002 wurde die Ehe geschieden und die elterliche Sorge für den gemeinsamen Sohn (geb. 1997) der Mutter zugesprochen. Seit dem 25. Oktober 2002 verfügte X._ über die Niederlassungsbewilligung (zuletzt kontrollbefristet bis 13. Juni 2008). Am 20. April 2004 heiratete er die serbische Staatsangehörige Y._ (geb. 1976), der gestützt auf die Heirat eine Aufenthaltsbewilligung (letztmals verlängert bis zum 19. April 2008) erteilt wurde. Die beiden aus dieser Ehe hervorgegangenen Kinder A._ (geb. 2005) und B._ (geb. 2006) wurden in die Niederlassungsbewilligung von X._ einbezogen. B. Am 4. Mai 2007 meldete sich X._ mit seiner Familie beim Einwohneramt H._ per 31. Mai 2007 nach Serbien und Montenegro ab. Er liess sich sein Pensionskassenguthaben wegen Ausreise ins Ausland auszahlen. Nach eigenen Angaben verliess die Familie am 23./24. Mai 2007 die Schweiz. Am 27. Oktober 2007 kehrte sie über Frankreich wieder zurück und am 1. November 2007 unterzeichneten die Eheleute X._ - Y._ bei der Einwohnerkontrolle Gesuchsformulare betreffend Erteilung einer Niederlassungs- bzw. Aufenthaltsbewilligung. Das Migrationsamt der Sicherheitsdirektion des Kantons Zürich teilte X._ und seiner Familie mit, dass sie den Entscheid im Ausland abzuwarten hätten, und wies die Stadtpolizei Winterthur an, eine Ausreisefrist anzusetzen und die Massnahme durchzusetzen. C. X._ ersuchte am 25. Januar 2008 das Migrationsamt des Kantons Zürich, entweder die Niederlassungs- und Aufenthaltsbewilligungen zu bestätigen oder einen anfechtbaren Entscheid darüber zu fällen, dass die Bewilligungen erloschen seien. Am 12. Februar 2008 forderte das Migrationsamt X._ auf, mit seiner Familie die Schweiz unverzüglich zu verlassen. Mit Eingabe vom 18. Februar 2008 an den Regierungsrat des Kantons Zürich beantragte X._, die Gültigkeit der Niederlassungs- bzw. Aufenthaltsbewilligungen festzustellen und der Beschwerde aufschiebende Wirkung zu erteilen. Die Staatskanzlei untersagte darauf superprovisorisch alle Vollzugshandlungen. D. Mit Verfügung vom 19. März 2008 stellte das Migrationsamt fest, dass die Niederlassungsbewilligungen von X._ und seiner Kinder sowie die Aufenthaltsbewilligung der Ehegattin erloschen seien, und wies die Gesuche um Wiedererteilung der Bewilligungen ab. Die Voraussetzungen für die Erteilung von Aufenthaltsbewilligungen aus wichtigen Gründen bzw. aufgrund eines Härtefalls erachtete es als nicht erfüllt und setzte den Betroffenen Frist zum Verlassen des Kantonsgebietes bis zum 2. Juni 2008. X._ rekurrierte dagegen an den Regierungsrat des Kantons Zürich. Mit Beschluss vom 9. Juli 2008 wies dieser den Rekurs ab und bestätigte sowohl das Erlöschen der früheren Bewilligungen als auch die Verweigerung der Erteilung von neuen Niederlassungs- bzw. Aufenthaltsbewilligungen. Die von X._ gegen den Regierungsratsbeschluss erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Entscheid vom 10. Dezember 2008 ab, soweit es darauf eintrat. E. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 3. Februar 2009 beantragt X._ Aufhebung des Entscheids des Verwaltungsgerichts vom 10. Dezember 2008 und Rückweisung an die Vorinstanz zwecks Feststellung des Nichterlöschens der Bewilligungen bzw. zwecks Erteilung der Aufenthaltsbewilligung an den Beschwerdeführer und seine Familie, eventualiter Feststellung des Nichterlöschens der Bewilligungen bzw. Billigungserteilung durch das Bundesgericht selber. Zudem stellt er das Begehren, der Beschwerde aufschiebende Wirkung zu erteilen. Die Staatskanzlei des Kantons Zürich - im Auftrag des Regierungsrates - und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. F. Mit Verfügung vom 13. Februar 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zuerkannt. G. Mit Eingaben vom 12. Juni bzw. 8. September 2009 meldete die Staatsanwaltschaft Winterthur/Unterland dem Bundesgericht eine Strafuntersuchung bzw. Anklageerhebung gegen X._ betreffend Vergehen gegen das Ausländergesetz.