Sachverhalt:
A. Der aus dem Kosovo stammende A.X._ (geb. 1969) reiste erstmals 1990 illegal in die Schweiz ein. Am 6. Januar 1993 wurde er im Rahmen der "Aktion Jugoslawien" (Bundesratsbeschluss vom 18. Dezember 1991) vorläufig aufgenommen. Am 23. August 2002 erhielt er die Niederlassungsbewilligung im Kanton Zürich. Zwei Monate später und sodann nochmals am 30. September 2003 ersuchte er um Bewilligung des Nachzugs seiner drei Kinder B.X._,C.X._ und D.X._ (geb. 1994, 1996 und 1998), welche die gleiche Staatsangehörigkeit besitzen wie er. Das Migrationsamt des Kantons Zürich (im Folgenden: Migrationsamt) verweigerte am 26. Mai 2005 den Nachzug der Kinder und widerrief die Niederlassungsbewilligung des Vaters. Den dagegen erhobenen Rekurs hiess der Regierungsrat des Kantons Zürich am 14. Dezember 2005 insoweit gut, als er den Widerruf der Niederlassungsbewilligung für ungültig erklärte und das Migrationsamt anwies, über das Familiennachzugsgesuch neu zu entscheiden.
Nach weiteren Sachverhaltsabklärungen wies das Migrationsamt das Nachzugsbegehren am 13. Juni 2006 wiederum ab. Die hiegegen im Kanton zunächst beim Regierungsrat und anschliessend beim Verwaltungsgericht erhobenen Rechtsmittel blieben erfolglos.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. November 2009 beantragen A.X._ und seine drei Kinder dem Bundesgericht, den in dieser Sache zuletzt ergangenen Entscheid des Verwaltungsgerichts vom 26. August 2009 aufzuheben und das Migrationsamt anzuweisen, den Kindern die Einreise sowie die Anwesenheit in der Schweiz zu bewilligen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht stellt den Antrag, die Beschwerde abzuweisen, soweit auf sie einzutreten ist. Der Regierungsrat, vertreten durch seine Staatskanzlei, sowie das Bundesamt für Migration beantragen Abweisung der Beschwerde. Das Migrationsamt hat sich nicht vernehmen lassen.

Erwägungen:
1. Auf die fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten, da der Ausschlussgrund des <ref-law> nicht greift. Gemäss dem hier noch anwendbaren Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG, BS 1 121; vgl. die Übergangsbestimmung des Art. 126 Abs. 1 AuG [SR 142.20]) haben die Beschwerdeführer grundsätzlich einen Anspruch auf Einbezug der Kinder in die Niederlassungsbewilligung des Vaters (Art. 17 Abs. 2 Satz 3 ANAG in der Fassung vom 23. März 1990, AS 1991 1034 1043). Sie können sich zudem auf das in Art. 8 Ziff. 1 EMRK und <ref-law> garantierte Recht auf Achtung des Familienlebens berufen, da die Beziehung zwischen dem Vater und den Kindern offenbar intakt ist. Ob dem Nachzugsanspruch letztlich stattzugeben ist, bildet eine Frage der materiellen Beurteilung (vgl. <ref-ruling> E. 1.1.5 S. 150 mit Hinweisen).
2. 2.1 Gemäss Art. 17 Abs. 2 Satz 3 ANAG haben ledige Kinder unter 18 Jahren Anspruch auf Einbezug in die Niederlassungsbewilligung, wenn sie mit ihren Eltern zusammenwohnen. Das gilt ohne weitere Bedingungen - abgesehen vom Vorbehalt des Rechtsmissbrauchsverbots und von Verstössen gegen die öffentliche Ordnung im Sinne von Art. 17 Abs. 2 Satz 4 ANAG - einzig für den Nachzug von gemeinsamen Kindern durch beide Eltern zusammen (<ref-ruling> E. 3.1.2 S. 14).
2.2 Der Beschwerdeführer 1 ist hier allerdings mit der Mutter der Kinder namens E._, die ebenfalls aus dem Kosovo stammt, nicht (zivilrechtlich) verheiratet. Er schloss mit ihr zwar in seiner Heimat Anfang 1993 eine sog. Imam-Ehe. In der Folge war er jedoch mit zwei Schweizerinnen (Eheschliessung im Jahr 1996 bzw. 2001) verheiratet; auf diese Ehen gestützt wurde ihm damals der Aufenthalt in der Schweiz bewilligt. Seit August 2006 ist er mit einer weiteren Landsfrau, welche in der Schweiz vorläufig aufgenommen war, standesamtlich verheiratet. Deshalb geht es vorliegend rechtlich nicht um die Zusammenführung einer Gesamtfamilie, sondern einer Teilfamilie. Daran ändert nichts, dass die Eltern der Kinder eine Zeit lang faktisch in der Schweiz zusammenlebten, da sie dies unter Umgehung des Gesetzes taten (s. dazu nachfolgende E. 4).
Da sich der Beschwerdeführer 1 seit 1990 in der Schweiz aufhält und die Kinder mit ihrer Mutter die Schweiz spätestens Ende 1999 verlassen haben, ist zudem - entgegen der Ansicht der Beschwerdeführer - von einem nachträglichen Familiennachzug auszugehen.
2.3 Unter diesen Umständen müssen für den Kindernachzug besondere familiäre Gründe bzw. eine zwingend nötig gewordene Änderung in den Betreuungsverhältnissen sprechen. Dies ist praxisgemäss nicht der Fall, wenn im Heimatland alternative Pflegemöglichkeiten bestehen, die dem Kindeswohl besser entsprechen, weil dadurch vermieden werden kann, dass die Kinder aus ihrer bisherigen Umgebung und dem ihnen vertrauten Beziehungsnetz gerissen werden. An den Nachweis der fehlenden Betreuungsmöglichkeit im Heimatland sind umso höhere Anforderungen zu stellen, je älter die nachzuziehenden Kinder sind bzw. je grösser die Integrationsschwierigkeiten erscheinen, die ihnen hier drohen (<ref-ruling> E. 3.1 S. 9 ff.; <ref-ruling> E. 3 S. 14 ff.; <ref-ruling> E. 2c S. 588 ff. mit Hinweisen). An dieser Praxis ist unter dem ANAG - entgegen der Meinung der Beschwerdeführer - festzuhalten, auch wenn sie unter der Herrschaft des neuen Ausländergesetzes (AuG) bei einem Nachzugsgesuch innert der Fristen des Art. 47 Abs. 1 AuG nicht mehr gilt (vgl. zu Art. 42 Abs. 1 und Art. 43 AuG: BGE 2C_270/2009 vom 15. Januar 2010 E. 4.7 und 4.8).
Im Übrigen erlöschen die Ansprüche auch beim nachträglichen Nachzug von Teilfamilien, wenn der Anspruchsberechtigte gegen die öffentliche Ordnung verstossen hat (Art. 17 Abs. 2 Satz 4 ANAG) oder Rechtsmissbrauch gegeben ist (vgl. Urteil 2C_289/2008 vom 30. September 2008 E. 2.5, in: ZBl 110/2009 S. 510).
Diese Grundsätze gelten sinngemäss auch für Ansprüche aus Art. 8 EMRK und <ref-law> (<ref-ruling> E. 3.1 S. 10).
3. 3.1 Die Vorinstanz ist der Auffassung, den Beschwerdeführern sei es nicht gelungen zu widerlegen, dass eine altersgerechte Betreuung der Kinder in ihrer Heimat nach wie vor gewährleistet sei und dem Kindeswohl besser entspreche als eine Übersiedlung in ein ihnen sowohl sprachlich als auch kulturell vollkommen fremdes Umfeld. Die Beschwerdeführer hätten namentlich nicht überzeugend dargelegt, welches Ereignis die massive Veränderung der Betreuungssituation verkörpere. Sie und die Kindsmutter hätten teilweise erklärt, Letztere pflege seit Ende 1999 keinen Kontakt mehr zu den Kindern. Andernorts sei der Jahreswechsel 2002/2003 bzw. die Heirat der Kindsmutter im Juni 2002 als Zeitpunkt angegeben, ab dem die Kindsmutter nicht mehr bereit gewesen sei, die Kinder zu betreuen. Der Beschwerdeführer 1 habe seine Kinder, die zwischen 1993 und 1999 zeitweise in der Schweiz gelebt hätten, im Dezember 1999 in die Heimat zurückkehren lassen, obwohl er bereits damals als Ehemann einer Schweizerin um Bewilligung des weiteren Aufenthaltes der Kinder gestützt auf Art. 8 EMRK hätte ersuchen können.
3.2 Die Beschwerdeführer wenden ein, im Jahre 1999 sei ein Nachzugsgesuch noch völlig aussichtslos gewesen, da die Mutter die Obhut über die Kinder damals nicht abgeben wollte. Erst im November 2002 habe die Mutter ausdrücklich bestätigt, dass sie sich nicht mehr um die Kinder sorgen werde. Die so entstandene Betreuungssituation habe der Vater nie gewollt.
4. 4.1 Die Beschwerdeführer verschweigen, dass das Migrationsamt die Aufenthaltsbewilligung des Beschwerdeführers 1 bereits am 28. Juli 1999 wegen rechtsmissbräuchlicher Berufung auf die im April 1996 mit einer Schweizerin eingegangene Ehe nicht mehr verlängert hatte. Seine dagegen im Kanton erhobenen Rechtsmittel blieben erfolglos und der Entscheid erwuchs in Rechtskraft. Das Verwaltungsgericht hielt seinerzeit fest, dass aufgrund der Umstände davon auszugehen sei, er habe eine Scheinehe mit der Schweizer Bürgerin geschlossen (E. 3d in fine des Urteils des Verwaltungsgerichts des Kantons Zürich vom 13. Juni 2001). Der Ausreiseverpflichtung entging der Beschwerdeführer 1 dadurch, dass er am 31. August 2001 die Ehe mit einer anderen Schweizerin einging. Daraufhin erhielt er im November 2001 eine neue Aufenthaltsbewilligung, welche das Migrationsamt auf seine Anfrage hin am 23. August 2002 durch eine Niederlassungsbewilligung ersetzte.
4.2 Was die Kindsmutter anbelangt, so hatte der Beschwerdeführer 1 für sie noch im Jahr 1993 um Einreise ersucht, damit beide ihre im selben Jahr geschlossene Imam-Ehe in der Schweiz leben könnten. Bevor darüber entschieden wurde, reiste Erstere im Sommer 1993 illegal in die Schweiz ein und ersuchte um Asyl. Ihr Asylgesuch wurde noch im selben Jahr abgewiesen und ab Februar 1994 galt sie als verschwunden. Ihren Angaben zufolge lebte sie bei den Eltern des Beschwerdeführers 1 und reiste mit den Kindern (geb. 1994, 1996 und 1998) erst im November 1998 wieder in die Schweiz ein, wo sie erneut ein Asylgesuch stellte, das am 11. August 1999 abgewiesen wurde. Wegen unzumutbaren Vollzugs der Wegweisung wurde sie gestützt auf den Bundesratsbeschluss vom 7. April 1999 zunächst vorläufig aufgenommen. Während ihres Aufenthaltes in der Schweiz lebte sie mit den Kindern beim Beschwerdeführer 1. Im Dezember 1999 kehrte sie mit ihnen im Rahmen des Rückkehrhilfeprogramms Kosovo in ihre Heimat zurück. Im Juni 2002 heiratete sie dort einen Landsmann, namens F._, der in der Schweiz niedergelassen war. Hierauf gestützt reiste sie im Januar 2003 wieder in die Schweiz ein und erhielt eine Aufenthaltsbewilligung. Gemäss den späteren Feststellungen der Behörden diente diese Eheschliessung jedoch ausschliesslich dem Zweck, ihren Aufenthalt in der Schweiz zu legalisieren, um sodann wieder mit dem Beschwerdeführer 1 zusammen zu leben. Namentlich unterzeichneten sie und der Beschwerdeführer 1 im Juli 2004 einen Mietvertrag über eine Wohnung in Zürich; auch gaben sie dabei als bisherige Anschrift eine gemeinsame Adresse in Glattbrugg an. Wegen rechtsmissbräuchlicher Berufung auf die Ehe mit F._ wurde der Kindsmutter mit Verfügung vom 26. Mai 2005 schliesslich der weitere Aufenthalt in der Schweiz verweigert. Sie focht die Verfügung nicht an und meldete sich per 23. Juni 2005 in den Kosovo ab.
5. 5.1 Vorstehende Ausführungen sprechen für sich. Gestützt hierauf erweist sich das Vorbringen der Beschwerdeführer als unglaubwürdig und als ungeeignet, eine von der Praxis geforderte Nachzugssituation (s. E. 2.3 hievor) zu begründen. Zwar scheiterte der Versuch des Migrationsamts, dem Beschwerdeführer 1 wegen dem Dargelegten auch die Niederlassungsbewilligung zu widerrufen. Der Regierungsrat stellte damals fest, dass die Behörde bei Erteilung der Niederlassungsbewilligung keine Untersuchungshandlungen vorgenommen hätte, obwohl es "geradezu auf der Hand" lag, dass dazu Anlass bestand. Daher könne von einem Erschleichen der Niederlassungsbewilligung durch falsche Angaben oder wissentliches Verschweigen im Sinne von Art. 9 Abs. 4 lit. a ANAG keine Rede sein. Weil die Niederlassungsbewilligung nicht aufgrund einer durch die neuerliche Ehe mit einer Schweizerin erlangten Rechtsposition erteilt worden sei, sei nicht von Belang, ob er sich diesbezüglich auf den für Ehegatten geltenden Bewilligungsanspruch nach Art. 7 ANAG berufen könne oder ob ihm insoweit Rechtsmissbrauch vorzuwerfen sei (Beschluss des Regierungsrats vom 14. Dezember 2005 E. 5c und d).
Deshalb verfügt der Beschwerdeführer 1 aufgrund eines heute rechtskräftigen Entscheids über die Niederlassungsbewilligung. Das allein genügt indes nicht, um den Familiennachzug durchzusetzen. Wenn er vorbringt, die Kindsmutter habe sich allmählich von den Kindern distanziert und diese ab dem Jahreswechsel 2002/2003 überhaupt nicht mehr betreuen wollen, so verschweigt er bewusst, dass die Kindsmutter damals unter Berufung auf eine mit einer dritten Person geschlossene Scheinehe bereits auf dem Weg zu ihm - dem Beschwerdeführer 1 - in den Kanton Zürich war. Beide planten letztlich unter Umgehung des Gesetzes eine Vereinigung der Eltern und der Kinder in der Schweiz. Dabei liessen sie die Kinder zunächst allein und im Endeffekt über einen längeren Zeitraum bei den Grosseltern väterlicherseits im Kosovo zurück. Bereits damals behaupteten sie aber, die Grosseltern seien aus gesundheitlichen Gründen nicht in der Lage, für die Kinder zu sorgen. Das hinderte sie jedoch nicht daran, die Kinder noch mindestens zweieinhalb Jahre - von der Einreise der Kindsmutter in die Schweiz im Januar 2003 bis zu ihrer Ausreise im Juni 2005 - den Grosseltern allein anzuvertrauen.
5.2 Demzufolge haben die Vorinstanzen zu Recht geschlossen, die Beschwerdeführer hätten nicht hinreichend belegt, dass eine altersgerechte Betreuung der Kinder in ihrer Heimat nicht (mehr) gewährleistet sei. Nichts anderes ergibt sich aus aktuelleren Arztberichten über die Grosseltern, zumal die Beschwerdeführer nicht darlegen, ob und was sich seit den früher ausgestellten Attesten im Wesentlichen verändert haben soll. Zudem sind die Kinder inzwischen älter und nicht mehr auf die gleiche Betreuung wie noch als Kinder im Vorschul- bzw. Primarschulalter angewiesen. Dass die Kindsmutter heute in der Tschechischen Republik wohnhaft sein soll, wo sie seit April 2007 gemeldet ist, ändert auch nichts, da die Kinder schon vorher über längere Zeit nur durch die Grosseltern betreut wurden.
5.3 Ob den Beschwerdeführern mit Blick auf vorstehende Ausführungen nicht auch zusätzlich Rechtsmissbrauch beim Kindernachzugsbegehren entgegenzuhalten ist, kann offen bleiben (vgl. erwähntes Urteil 2C_289/2008 vom 30. September 2008 E. 2.5 einerseits und Urteil 2A.46/2002 vom 23. Mai 2002 E. 3.4 in fine anderseits).
6. Die Beschwerdeführer beanstanden die Verfahrensdauer von mehreren Jahren und berufen sich auf Art. 10 der UNO-Kinderrechtskonvention vom 20. November 1989 (SR 0.107). Sicherlich ist die Verfahrensdauer vorliegend ausserordentlich lang. Die Vorinstanz hat denn auch zu Recht das zuletzt über zwei Jahre beim Regierungsrat dauernde Rekursverfahren beanstandet. Dem Verwaltungsgericht selber ist zur Verfahrensdauer aber kein Vorwurf zu machen. Was die vorherige längere Verfahrensdauer bis zu dem (letzten) am 12. Juli 2006 eingeleiteten Rekursverfahren anbelangt, so geht diese im Wesentlichen auf die dargelegte missbräuchliche Vorgehensweise der Eltern zurück. Im Übrigen führt eine allfällige Verletzung des Beschleunigungsgebots nicht zu einem absoluten Anspruch auf Familiennachzug (Urteil des Bundesgerichts 2A.414/2001 vom 5. Februar 2002 E. 5b/bb).
Soweit die Beschwerdeführer mit ihrer Rüge die Beurteilung nach dem neuen Ausländerrecht anstreben, ist ihnen für die Sachlage vor dem Jahr 2008 ohnehin die übergangsrechtliche Vorschrift des Art. 126 Abs. 1 AuG entgegenzuhalten. Diese sieht keine Rückwirkung des neuen Rechts vor. Daher kann Letzteres nicht bereits auf die im Jahr des ursprünglichen Nachzugsbegehrens geltende Situation angewendet werden. Dessen Anwendung kommt höchstens für einen (nicht abgeschlossenen) Sachverhalt in Frage, der im Zeitpunkt des Inkrafttretens des Ausländergesetzes am 1. Januar 2008 (fort-)besteht (vgl. Urteil 2C_168/2009 vom 30. September 2009 E. 4.1 und 4.2). Gerade mit Blick auf die lange Verfahrensdauer hätten die Beschwerdeführer dazu aber nach dem soeben genannten Datum einen neuen Antrag bei den zuständigen Behörden zwecks Prüfung der aktuellen Sachlage nach dem in Kraft getretenen Recht stellen können und insoweit den kantonalen Instanzenzug erschöpfen müssen. Das haben sie bisher nicht getan. Deshalb erübrigt sich, das Nachzugsbegehren vorliegend nach neuem Recht zu beurteilen. Insoweit ergibt sich entgegen der Ansicht der Beschwerdeführer kein Verstoss gegen den Grundsatz der Rechtsgleichheit nach <ref-law>.
7. Nach dem Dargelegten ist die Beschwerde abzuweisen.
Diesem Ausgang entsprechend haben die Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 sowie Art. 66 Abs. 1 und 5 BGG). Parteientschädigungen werden nicht geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern zu gleichen Teilen und unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 6. Mai 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Merz