Sachverhalt: A. A.a Die 1977 geborene mazedonische Staatsangehörige X._ heiratete am 4. Januar 1994 in Mazedonien ihren in der Schweiz niederlassungsberechtigten Landsmann Y._. Sie reiste am 12. August 1994 in die Schweiz ein und erhielt hier am 2. September 1994 eine Aufenthaltsbewilligung, welche in der Folge wiederholt verlängert wurde. Aus der Ehe gingen die beiden Kinder A._ (geboren 1995) und B._ (geboren 1997) hervor, welche in die Niederlassungsbewilligung des Vaters miteinbezogen wurden. Am 3. April 1999, d.h. nach einem Aufenthalt von weniger als fünf Jahren, verliess X._ die eheliche Wohnung; gegenüber den Behörden gab sie an, Opfer von häuslicher Gewalt geworden zu sein. Am 1. April 2000 kehrte X._ mit ihren Kindern ein erstes Mal nach Mazedonien zurück. A.b Gemeinsam reisten sie am 13. August 2001 wieder in die Schweiz ein, worauf X._ erneut eine Aufenthaltsbewilligung erteilt wurde. Im Sommer 2003 reiste X._ mit den beiden Kindern abermals nach Mazedonien aus. Am 28. Oktober 2003 wurde die Ehe zwischen X._ und Y._ in Mazedonien geschieden. Das zuständige Gericht unterstellte die gemeinsamen Kinder der elterlichen Sorge des Vaters. A.c Ohne ihre Kinder reiste X._ am 27. Februar 2004 ein weiteres Mal in die Schweiz ein. Unter Hinweis darauf, dass ihr "Ehemann" über eine Niederlassungsbewilligung verfüge, stellte sie hier ein Gesuch um Erteilung einer Aufenthaltsbewilligung. Das Migrationsamt des Kantons Zürich wies dieses Bewilligungsgesuch am 6. Juli 2004 ab. Ein Rekurs von X._ wurde vom Regierungsrat des Kantons Zürich am 20. Juni 2006 abgewiesen. A.d Zuvor, am 2. Juli 2005, waren bereits die beiden Kinder von X._ in die Schweiz zurückgekehrt. Sie wurden erneut in die Niederlassungsbewilligung ihres Vaters einbezogen. B. Am 1. September 2006, rund zwei Monate nach dem abschlägigen Rekursentscheid des Regierungsrates, richtete X._ ein Wiedererwägungsgesuch an das kantonale Migrationsamt und ersuchte dieses, auf seinen negativen Bewilligungsentscheid vom 6. Juli 2004 zurückzukommen. Sie machte geltend, dass sie einen Suizidversuch verübt habe, da ein Leben in Mazedonien ohne ihre Kinder für sie unvorstellbar sei. Zudem habe sie eine Neuregelung des Besuchsrechts gegenüber ihren Kindern beantragt, weshalb eine Intensivierung der gegenseitigen Beziehung zu erwarten sei. Mit Verfügung vom 7. September 2006 trat das Migrationsamt auf das Wiederwägungsgesuch nicht ein. Es begründete dies damit, dass X._ keine wesentlich veränderten Tatsachen vorbringe, sondern sich nahezu ausschliesslich auf eine andere Würdigung der bekannten Umstände beschränke. C. Gegen den Nichteintretensentscheid des Migrationsamtes rekurrierte X._ erneut beim Regierungsrat des Kantons Zürich, welcher den Rekurs mit Beschluss vom 1. Oktober 2008 abwies. Hierauf beschwerte sich X._ ohne Erfolg beim Verwaltungsgericht des Kantons Zürich: Dieses wies die Beschwerde mit Urteil vom 1. April 2009 ab. D. Mit Eingabe vom 22. Mai 2009 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragt im Wesentlichen, es sei der angefochtene Entscheid aufzuheben und das Migrationsamt des Kantons Zürich anzuweisen, auf ihr Wiedererwägungsgesuch einzutreten. Der Regierungsrat und das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Mit Verfügung vom 27. Mai 2009 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. 