Sachverhalt:
A. Der aus dem Kosovo stammende X._ (geb. 1982) erhielt am 15. Mai 2000 im Rahmen des Familiennachzuges die Aufenthaltsbewilligung. Am 11. Mai 2006 heiratete er eine Schweizer Bürgerin (geb. 1988). In der Schweiz hatte er bereits als Jugendlicher wiederholt zu schweren Klagen Anlass gegeben und später fortlaufend delinquiert, wofür er mehrfach zu Bussen und Freiheitsstrafen verurteilt wurde; zuletzt zu 2 1/2 Jahren Zuchthaus u.a. wegen gewerbsmässigen Diebstahls und Raubes (mit besonderer Gefährlichkeit). Am 24. Juli 2006 verfügte das Amt für Migration des Kantons Luzern deshalb die Ausweisung von X._ auf den Zeitpunkt seiner Entlassung aus dem Strafvollzug.
Mit Urteil vom 10. Juli 2007 hiess das Verwaltungsgericht des Kantons Luzern eine Beschwerde gegen die Ausweisungsverfügung insoweit gut, als X._ nicht auszuweisen, sondern - im Sinne einer milderen Massnahme - bloss wegzuweisen sei. Im Übrigen wies das Gericht die Beschwerde ab. Es erwog im Wesentlichen, der gemäss Art. 7 ANAG durch Heirat erworbene Anspruch auf Verlängerung der Aufenthaltsbewilligung sei erloschen; ausserdem erweise sich deren Nichtverlängerung auch als verhältnismässig. Die gegen dieses Urteil erhobene Beschwerde in öffentlich-rechtlichen Angelegenheiten wies das Bundesgericht mit Urteil 2C_493/2007 vom 18. Februar 2008 ab, soweit es darauf eintrat.
B. Anstatt auszureisen, stellte X._ mit Eingabe vom 28. März 2008 beim Amt für Migration des Kantons Luzern zuhanden des Bundesamtes für Migration gestützt auf Art. 83 des am 1. Januar 2008 in Kraft getretenen Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) ein Gesuch um vorläufige Aufnahme. Mit Eingabe vom 24. April 2008 stellte X._ beim kantonalen Amt für Migration ausserdem ein "Anpassungsgesuch nach Art. 5 VRG (...) betreffend Aufenthaltsbewilligung (alt Art. 7 Abs. 1 ANAG)" mit den Anträgen, ihm - dem Gesuchsteller - eine Aufenthaltsbewilligung zu erteilen, eventuell auf seine Wegweisung zu verzichten. Zur Begründung machte er geltend, die Rechts- und Sachlage habe sich inzwischen wesentlich verändert: Aufgrund der Unabhängigkeitserklärung des Kosovo und aufgrund der völkerrechtlichen Anerkennung dieses Staates hätten sich die internationalen Sicherheits- und Hilfsorganisationen aus dem betroffenen Gebiet zurückgezogen mit der Folge, dass der Minderheitenschutz für ihn als Angehöriger der Ashkali-Volksgruppe nicht mehr gewährleistet sei und er im Falle einer Rückkehr in den Kosovo dort "absolut keine Überlebenschance" mehr habe und er "der wirtschaftlichen und sozialen Existenz grundlegend beraub(t)" würde.
C. Mit Verfügung vom 14. Mai 2008 ordnete das Amt für Migration des Kantons Luzern die Wegweisung von X._ an und führte zu den gestellten Begehren um vorläufige Aufnahme bzw. um Anpassung der ursprünglichen Verfügung aus, die beiden Gesuche würden "nach Rechtskraft der kantonalen Wegweisungsverfügung" zur Prüfung an das Bundesamt für Migration weitergeleitet
Eine hiegegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Luzern am 13. März 2009 ab, soweit es darauf eintrat. Es erwog im Wesentlichen, soweit X._ eine Aufenthaltsbewilligung beantrage, überschreite er den Streitgegenstand, weshalb auf die Beschwerde insofern nicht einzutreten sei. Die angefochtene Wegweisungsverfügung des kantonalen Migrationsamtes stufte das Gericht als Vollstreckungsverfügung (ordentliche Wegweisung nach Art. 66 AuG) ein und wies das Begehren um deren Aufhebung ab.
D. Mit Eingabe vom 4. Mai 2009 führt X._ beim Bundesgericht "Beschwerde/Subsidiäre Verwaltungsbeschwerde (recte: Verfassungsbeschwerde) in öffentlich-rechtlichen Angelegenheiten nach <ref-law>/<ref-law> betreffend Aufenthalt" mit den Anträgen, das Urteil des Verwaltungsgerichts des Kantons Luzern vom 13. März 2009 aufzuheben und die Sache zur Neubeurteilung an das kantonale Amt für Migration (eventuell an das Verwaltungsgericht) zurückzuweisen.
Das kantonale Migrationsamt beantragt, die Beschwerde abzuweisen. Denselben Antrag stellen das Verwaltungsgericht des Kantons Luzern und das Bundesamt für Migration.
E. Mit Verfügung vom 7. Mai 2009 hat der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt.
F. Mit Eingabe vom 16. Juli 2009 hat sich X._ noch einmal unaufgefordert an das Bundesgericht gewandt.

Erwägungen:
1. 1.1 Das Bundesgericht prüft seine Zuständigkeit bzw. Art und Zulässigkeit von Rechtsmitteln von Amtes wegen und mit freier Kognition (vgl. <ref-law>; <ref-ruling> E. 2 S. 188, 300 E. 1.2 S. 302; je mit Hinweisen). Vorweg ist die Zulässigkeit der Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> zu prüfen, welche gegenüber der subsidiären Verfassungsbeschwerde das prinzipale Rechtsmittel darstellt (vgl. <ref-law>: "soweit keine Beschwerde nach den Artikeln 72-89 zulässig ist").
1.2 Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Das Rechtsmittel ist ferner ausgeschlossen gegen die Wegweisung (vgl. <ref-law>).
1.3 Die dem angefochtenen kantonal letztinstanzlichen Endentscheid zu Grunde liegende Wegweisung durch das kantonale Migrationsamt kann nach dem Gesagten nicht Gegenstand der Beschwerde in öffentlich-rechtlichen Angelegenheiten sein. Der Beschwerdeführer hat aber - als Ausländer, der mit einer Schweizerin verheiratet ist - im Grundsatz einen Anspruch auf Erteilung und Verlängerung seiner Aufenthaltsbewilligung (vgl. Art. 7 Abs. 1 ANAG bzw. Art. 42 Abs. 1 AuG), womit der Weg der Beschwerde in öffentlich-rechtlichen Angelegenheiten insoweit geöffnet ist. Doch wurde in früheren Verfahren bereits rechtskräftig entschieden, dass dieser Anspruch bei der gegebenen Sachlage aufgrund der vorbehaltenen rechtlichen Schranken nicht geltend gemacht werden kann. Soweit der Betroffene - wie dies der Beschwerdeführer tut - in einem neuen Verfahren rügen will, die verlangte nochmalige Beurteilung seines Anspruches auf Verlängerung seiner Aufenthaltsbewilligung werde von der kantonalen Behörde durch eine bundesrechtswidrige Anwendung der kantonalen Revisionsregeln oder durch Missachtung des bundesverfassungsrechtlichen Anspruchs auf Neubeurteilung (Wiedererwägung) bei Vorliegen von wesentlichen neuen Tatsachen oder Beweismitteln oder bei wesentlicher nachträglicher Änderung der Sach- oder Rechtslage zu Unrecht verweigert (<ref-ruling> E. 3a S. 6 mit Hinweisen; zur Rechtslage unter der neuen Bundesverfassung <ref-ruling> E. 6 S. 137 f. ), steht ihm, wie schon unter der Herrschaft des Bundesgesetzes vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege (OG), das ordentliche Rechtsmittel - heute die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> - zur Verfügung (vgl. Urteil 2.C_159/2007 vom 2. August 2007, E. 1.2). Als solche ist die Eingabe des Beschwerdeführers vom 4. Mai 2009 entgegenzunehmen und zu behandeln; für die subsidiäre Verfassungsbeschwerde gemäss <ref-law> besteht dagegen nach dem Gesagten kein Raum.
2. 2.1 Die Wiedererwägung von Verwaltungsentscheiden, die in Rechtskraft erwachsen sind, kann nicht beliebig zulässig sein. Sie darf namentlich nicht dazu dienen, rechtskräftige Verwaltungsentscheide immer wieder in Frage zu stellen oder die Fristen für die Ergreifung von Rechtsmitteln zu umgehen. Auch bei negativen Verfügungen scheidet eine Wiedererwägung aus, wenn den Behörden kurze Zeit nach einem abgelehnten Gesuch erneut ein identisches Gesuch unterbreitet wird (<ref-ruling> E. 2b S. 47 mit Hinweisen).
2.2 Eine kantonale Behörde muss sich mit einem Wiedererwägungsgesuch dann förmlich befassen und allenfalls auf eine rechtskräftige Verfügung zurückkommen, wenn das kantonale Recht dies vorsieht und die entsprechenden gesetzlichen Voraussetzungen erfüllt sind oder wenn unmittelbar aus der Bundesverfassung fliessende Grundsätze dies gebieten (vgl. hierzu: <ref-ruling> E. 2b S. 46/47; <ref-ruling> E. 3a S. 150 ff.; <ref-ruling> E. 4c S. 253; <ref-ruling> E. 3 S. 371 ff.).
Ob das Wiedererwägungsgesuch (bzw. "Anpassungsgesuch") vorliegend von den kantonalen Behörden hätte materiell behandelt werden müssen, hängt demnach davon ab, ob sich der Sachverhalt seit Beurteilung des ersten Streites um die Verlängerung der Aufenthaltsbewilligung des Beschwerdeführers derart wesentlich geändert hat, dass ein anderes Ergebnis der Interessenabwägung in Betracht fallen könnte (vgl. Urteil 2A.476/2005 vom 9. Mai 2006, E. 2).
2.3 Der Beschwerdeführer macht geltend, im "Anpassungsgesuch" vom 24. April 2008 habe er auf die völlig neuen Verhältnisse hingewiesen, die sich nach der Unabhängigkeitserklärung des Kosovo und der darauf folgenden völkerrechtlichen Anerkennung dieses Staates dort ergeben hätten. Er rügt, unter diesen Umständen wären die kantonalen Behörden verpflichtet gewesen, seine Situation zu überprüfen und über die Frage der Verlängerung seiner Aufenthaltsbewilligung neu zu befinden.
2.4 Wieweit das kantonale Migrationsamt das Gesuch vom 24. April 2008 hätte an die Hand nehmen müssen und wieweit das Verwaltungsgericht die Frage hätte behandeln sollen, ob die behaupteten veränderten Umstände im Kosovo bei der Interessenabwägung zu einer abweichenden Beurteilung Anlass geben, kann vorliegend offen bleiben: Zwar ist dem Verwaltungsgericht entgegenzuhalten, dass - entgegen seiner Auffassung - das erwähnte Gesuch im verwaltungsgerichtlichen Beschwerdeverfahren sehr wohl Streitgegenstand bildete, war doch die erste Instanz mit dem Begehren um Wiedererwägung der Bewilligungsfrage infolge veränderter Umstände befasst bzw. hiefür angerufen worden und durfte der Beschwerdeführer, nachdem diesem Begehren nicht entsprochen worden war, dem Verwaltungsgericht zulässigerweise einen entsprechenden Antrag stellen. Eine Aufhebung des angefochtenen Entscheides rechtfertigt sich aber nicht. Denn der Beschwerdeführer hatte bereits in seiner Beschwerde vom 14. August 2006 gegen die Ausweisungsverfügung geltend gemacht, er werde in seiner Heimat keine Aussicht auf wirtschaftliche Integration haben, wovon im Übrigen auch das Verwaltungsgericht in seinem (ersten) Urteil vom 10. Juli 2007 ausging. Wenn nun neu, unter Berufung auf die Ausrufung der Unabhängigkeit des Kosovos - am 17. Februar 2008 - und die völkerrechtliche Anerkennung derselben durch die Schweiz - am 27. Februar 2008 -, noch einmal auf diese Schwierigkeiten hingewiesen wird, sind dies keine relevant anderen Umstände als jene, welche dem (vom Bundesgericht geschützten) Urteil vom 10. Juli 2007 zu Grunde lagen.
Auch der Umstand, dass der Beschwerdeführer zur albanisch sprechenden Minderheit der Ashkali gehört, ist keine relevante Änderung der Sach- oder Rechtslage: Zur Situation der Ashkali vor der Unabhängigkeitserklärung des Kosovo hat der Beschwerdeführer im Gesuch vom 28. März 2008 ausgeführt, die internationalen Truppen vermöchten der genannten Minderheit keinen Schutz zu gewähren ("Die Übergriffe der albanischen Bevölkerung auf die albanisch sprechenden Roma, Ashkali und Ägyptern können die internationalen Sicherheitskräfte, die in Kosovo stationiert sind, nicht verhindern [EMARK 2006 Nr. 10]"). Auch hier ist nicht ersichtlich, inwiefern die Ausrufung der Unabhängigkeit zu einer rechtlich relevanten Änderung für die Interessenabwägung hätte führen können.
3. Nach dem Gesagten erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten - soweit sie überhaupt offen steht - als unbegründet. Sie ist abzuweisen, soweit darauf eingetreten werden kann.
Dem Verfahrensausgang entsprechend sind die Gerichtskosten (<ref-law>) dem Beschwerdeführer aufzuerlegen (<ref-law>). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Migration und dem Verwaltungsgericht des Kantons Luzern sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 28. Oktober 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Klopfenstein