Sachverhalt: A. X._ - damals noch den Familiennamen Q._ führend - (geb. 1980) und ihre Tochter Y._ (geb. 2000), beide ukrainische Staatsangehörige, reisten im Juni 2002 illegal in die Schweiz ein. Die von ihnen anschliessend gestellten Asylgesuche blieben erfolglos. Im September 2005 heiratete X._ den österreichischen Staatsangehörigen F._ (geb. 1961), der im Kanton Schwyz über eine Aufenthaltsbewilligung EG/EFTA verfügte. Mit Blick darauf wurde vom weiteren Vollzug der rechtskräftig angeordneten Wegweisung abgesehen und X._ sowie Y._ für fünf Jahre (bis 8. September 2010) gültige Aufenthaltsbewilligungen - jedoch nicht wie von ihnen im bundesgerichtlichen Verfahren behauptet Niederlassungsbewilligungen - erteilt. Nachdem sich das Ehepaar getrennt hatte, widerrief die Fremdenpolizei des Kantons Schwyz am 16. Juni 2008 die Aufenthaltsbewilligungen wegen rechtsmissbräuchlicher Berufung auf eine nur noch formell bestehende Ehe. Das dagegen erhobene Rechtsmittel wies der Regierungsrat des Kantons Schwyz am 2. September 2008 ab. Auf die anschliessend eingereichte Beschwerde trat das Verwaltungsgericht des Kantons Schwyz mit Entscheid vom 10. Oktober 2008 wegen Versäumung der Rechtsmittelfrist nicht ein. B. Am 24. Oktober 2008 ersuchten X._ und Y._ die kantonale Fremdenpolizei, die Verfügung vom 16. Juni 2008 zu "widerrufen" oder eventualiter ihnen eine neue Aufenthaltsbewilligung zu erteilen. Sie begründeten dieses Gesuch mit einer veränderten Situation: X._ wisse nun, dass sie schwanger sei; der voraussichtliche Geburtstermin sei der 8. Januar 2009; auch sei eine gemeinsame Zukunft mit dem Vater des erwarteten Kindes, einem im Kanton Luzern niedergelassenen Staatsangehörigen von Serbien- Montenegro namens G._ (geb. 1980), geplant. Am 3. November 2008 verfügte das Amt für Migration des Kantons Schwyz, dass auf die erwähnten Anträge nicht eingetreten werde. Diesen Entscheid zogen X._ und Y._ an den Regierungsrat weiter, mit dem Antrag, die Verfügung des Amtes für Migration aufzuheben und dieses "anzuweisen, das mit Eingabe vom 24.10.2008 gestellte Wiedererwägungsgesuch materiell zu behandeln". Der Regierungsrat wies die Beschwerde am 25. November 2008 ab. Er erklärte, dass eine Wiedererwägung nicht in Betracht komme. Allerdings liege in der geltend gemachten Beziehung zu einem Ausländer mit Niederlassungsbewilligung nach ausländerrechtlicher Optik eine neue Begründung für die Erteilung einer Aufenthaltsbewilligung vor. Deshalb hätte das Amt für Migration auf das Gesuch vom 24. Oktober 2008 eintreten und materiell darüber entscheiden müssen, ob neue Aufenthaltsbewilligungen erteilt werden könnten. Aus "verfahrensökonomischen" Gründen verzichtete der Regierungsrat indes auf eine Rückweisung an die Vorinstanz und nahm selber die materielle Beurteilung vor. Er lehnte die Erteilung einer Aufenthaltsbewilligung allerdings ab, da X._ noch nicht von F._ geschieden und mit G._ nicht verheiratet sei; ausserdem werde Letzterer ohnehin erst den Nachweis erbringen müssen, dass er tatsächlich der Vater des - damals noch - ungeborenen Kindes ist. C. Dagegen gelangten X._ und Y._ am 16. Dezember 2008 an das Verwaltungsgericht mit dem Antrag, "der angefochtene Entscheid sei aufzuheben und es sei das Amt für Migration in Gutheissung der Beschwerde anzuweisen, auf das Wiedererwägungsbegehren der Beschwerdeführerinnen vom 24.10.2008 einzutreten, eventualiter sei den Beschwerdeführerinnen in Gutheissung der Beschwerde die nachgesuchte Bewilligung zu erteilen". Das Verwaltungsgericht wies die Beschwerde mit Entscheid vom 5. Februar 2009 "im Sinne der Erwägungen" ab. Es erwog, dass das Amt für Migration am 3. November 2008 zurecht nicht auf das Gesuch von X._ und Y._ vom 24. Oktober 2008 eingetreten sei. Die Argumente "Schwangerschaft" und "neuer Lebenspartner" hätten schon im ersten Verfahren beim Regierungsrat im Sommer 2008 vorgebracht werden müssen. In einer Eventualbegründung führte das Verwaltungsgericht aus, dass der neue Lebenspartner seinen gesetzlichen Wohnsitz im Kanton Luzern habe, weshalb ein von ihm abgeleitetes Aufenthaltsrecht mit einem dort zu stellenden Gesuch zu beantragen sei. Selbst wenn die Vorinstanzen auf das Gesuch einzutreten gehabt hätten, bestehe daher kein Bewilligungsanspruch, wobei es ergänzend auf die Darlegungen des Regierungsrates verwies. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 9. März 2009 beantragen X._ und Y._ dem Bundesgericht, die Entscheide des Verwaltungsgerichts vom 5. Februar 2009, des Regierungsrates vom 25. November 2008 und des Amtes für Migration vom 3. November 2008 aufzuheben und die letztgenannte Behörde anzuweisen, auf das "Wiedererwägungsbegehren" vom 24. Oktober 2008 einzutreten und die nachgesuchten Bewilligungen zu erteilen. E. Der Regierungsrat stellt den Antrag, die Beschwerde abzuweisen, soweit auf sie überhaupt einzutreten sei. Das Verwaltungsgericht und das Bundesamt für Migration ersuchen um Abweisung der Beschwerde. Das kantonale Amt für Migration hat auf eine Vernehmlassung verzichtet. F. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde am 16. März 2009 antragsgemäss die aufschiebende Wirkung zuerkannt.