A.

A.a Der aus Palästina (Westbank) stammende X., geb. 1969, reiste am 25. Juni 1996 in die Schweiz ein, wo er um Asyl ersuchte. Das Gesuch wurde am 11. November 1998 abgewiesen. Am 8. September 1998 wurde X. wegen Betäubungsmitteldelikten mit 18 Monaten Gefängnis bei bedingtem Vollzug und mit einer Landesverweisung für die Dauer von sieben Jahren bestraft. Die in der Folge angeordnete Ausschaffungshaft führte nicht zum Ziel, da die Ausschaffung mangels Reisepapieren nicht vollzogen werden konnte. Der danach ergangenen Aufforderung, die Schweiz selbständig zu verlassen, kam X. nicht nach. Am 25. Mai 2000 verurteilte ihn das Obergericht des Kantons Zürich erneut wegen Betäubungsmitteldelikten sowie wegen falschen Zeugnisses zu zehn Monaten Gefängnis unbedingt. Gleichzeitig ordnete es den Vollzug der bedingt ausgefällten Gefängnisstrafe vom 8. September 1998 an. Vom 19. September 1999 bis zum 12. November 2001 befand sich X. zuerst in Untersuchungshaft und später im Strafvollzug.

A.b Am 13. September 2002 ersuchte der Kanton Zürich das zuständige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration), X. vorläufig aufzunehmen. Das Gesuch wurde am 15. Juli 2003 abgewiesen. Eine dagegen beim Eidgenössischen Justiz- und Polizeidepartement eingereichte Beschwerde ist noch immer (seit dem 1. Januar 2007 beim Bundesverwaltungsgericht) hängig.

A.c Im Mai 2007 liess sich X. von seiner ersten in Palästina lebenden Ehefrau scheiden, und am 29. Juni 2007 heiratete er die in der Schweiz niedergelassene spanische Staatsangehörige Y., geb. 1978. Diese Ehe blieb bisher kinderlos. X. ist hingegen Vater von zwei in Palästina bei der Mutter lebenden Söhnen, die in den Jahren 1991 und 1993 geboren wurden.

A.d Vom 1. Dezember 1997 bis zum 31. Juli 1998 arbeitete X. als Küchenhilfe in einem Restaurant in Zürich. Nach der Entlassung aus dem Strafvollzug war er vom 7. Januar 2002 bis zum 11. Februar 2002 als Office-Mitarbeiter in einem Restaurantbetrieb und vom 11. Februar bis zum 12. März 2002, als ihm ein Arbeitsverbot auferlegt wurde, als Pizzaiolo in einem anderen Restaurant erwerbstätig. Danach war er im Rahmen des Programms "Gemeinnützige Einsatzpläne der Stadt Zürich" am Empfang der Asylorganisation der Stadt Zürich aktiv. Seit Anfang 2008 arbeitet er als Sicherheitsbeamter und Detektiv bei einer privaten Unternehmung im Sicherheitsbereich.

A.e Mit Strafbefehl vom 10. März 2008 wurde X. wegen Mitführens von Waffen und Munition ohne Waffentragbewilligung mit einer bedingten Geldstrafe von zwei Tagessätzen zu Fr. 70.- und mit einer Busse von Fr. 300.- bestraft.

B. Mit Verfügung vom 7. September 2007 wies das Migrationsamt des Kantons Zürich ein Gesuch von X. um Erteilung einer Aufenthaltsbewilligung EG/EFTA zum Verbleib bei seiner Ehefrau ab und setzte ihm eine Frist zum Verlassen des schweizerischen Staatsgebietes. (...)

C. Am 13. August 2008 wies der Regierungsrat des Kantons Zürich einen dagegen erhobenen Rekurs ab. Mit Urteil vom 21. Januar 2009 wies das Verwaltungsgericht des Kantons Zürich, 2. Kammer, eine dagegen eingereichte Beschwerde ab. (...)

D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 23. März 2009 stellen X. und Y. in der Sache die folgenden Rechtsbegehren:

Zur Begründung wird im Wesentlichen eine Verletzung des Freizügigkeitsrechts geltend gemacht. Die Staatskanzlei (für den Regierungsrat) des Kantons Zürich schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Migration stellt ebenfalls Antrag auf Abweisung und führt dazu aus, das Freizügigkeitsrecht vermittle X. und Y. keinen Anspruch auf Anwesenheitsbewilligung. (...)

(Auszug)

1.1 Nach Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts über Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.

1.2 Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) in Kraft getreten. Nach Art. 126 AuG bleibt das alte Recht (Bundesgesetz vom 26. Mai 1931 über Aufenthalt und Niederlassung der Ausländer [ANAG] und Ausführungserlasse) anwendbar auf Gesuche, die vor dem Inkrafttreten des neuen Gesetzes eingereicht worden sind. Das Verfahren richtet sich jedoch nach dem neuen Recht. Im vorliegenden Verfahren ist in materiell-rechtlicher Hinsicht auf das alte Recht abzustellen, da das Bewilligungsgesuch noch vor dem 1. Januar 2008 eingereicht wurde (BGE 135 I 142 E. 1.2 S. 145).

1.3 Die Beschwerdeführerin verfügt über die Niederlassungsbewilligung, weshalb ihr Ehemann nach Art. 17 Abs. 2 ANAG (AS 1991 1043) einen Anspruch auf Erteilung der Aufenthaltsbewilligung hat, solange die Ehegatten zusammenwohnen. Überdies können sich die Beschwerdeführer auf Art. 8 EMRK bzw. Art. 13 BV berufen, soweit ihre Ehe intakt ist und tatsächlich gelebt wird, was an sich von keiner Seite bestritten wird. In erster Linie machen sie aber geltend, sie hätten einen Anspruch auf Familienvereinigung gestützt auf das Freizügigkeitsrecht (Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit [FZA; SR 0.142.112.681]). Da bereits gestützt auf Art. 17 Abs. 2 ANAG und Art. 8 EMRK bzw. Art. 13 BV ein Anspruch auf Bewilligung besteht, ist auf die Beschwerde ohnehin einzutreten, weshalb hier die Anwendbarkeit des Freizügigkeitsrechts einzig unter materiellen Gesichtspunkten geprüft zu werden braucht.

1.4 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht - inklusive Bundesverfassungsrecht -, Völkerrecht sowie kantonale verfassungsmässige Rechte (Art. 95 BGG). Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 97 Abs. 1 bzw. Art. 105 Abs. 2 BGG).

2.1 Die Beschwerdeführer machen in verschiedener Hinsicht geltend, das Verwaltungsgericht habe den Sachverhalt offensichtlich unrichtig oder unter Verletzung ihres Anspruchs auf rechtliches Gehör festgestellt.

2.2 Im angefochtenen Entscheid hält die Vorinstanz fest, die bald dreizehnjährige Anwesenheitsdauer des Beschwerdeführers ergebe sich allein daraus, dass dieser seine Mitwirkungspflicht verletzt und sich seiner Ausschaffung widersetzt habe. Diese Feststellung widerspricht offenkundig den Akten. Daraus geht nämlich hervor, dass die Ausschaffung palästinensischer Bürger ein komplexes Zusammenwirken der schweizerischen, palästinensischen und israelischen Behörden erfordert, das im vorliegenden Fall (wenigstens bisher) anscheinend nicht erfolgreich war. Das kantonale Migrationsamt hat denn auch dem zuständigen Bundesamt am 13. September 2002 die vorläufige Aufnahme des Beschwerdeführers beantragt, weil es trotz aller Bemühungen keine konkreten Hinweise dafür gebe, dass die Ausschaffung in absehbarer Zeit möglich werde. In seinem Entscheid vom 15. Juli 2003 hielt zwar das Bundesamt für Flüchtlinge unter anderem fest, der Beschwerdeführer könne sich über seine Familie einen Reisepass der Autonomiebehörde ausstellen lassen, weshalb er seine Mitwirkungspflicht verletzt habe, soweit er dies unterlassen habe. Dieser Entscheid ist aber nicht rechtskräftig; vielmehr ist nunmehr seit rund sechs Jahren eine dagegen erhobene Beschwerde hängig. Es kann daher nicht ohne weiteres davon ausgegangen werden, der Beschwerdeführer trage allein die Verantwortung für das bisherige Scheitern der Ausschaffung.

2.3 Die Beschwerdeführer rügen, die kantonalen Instanzen hätten die im Rekursverfahren vor dem Regierungsrat eingereichten zahlreichen Referenzschreiben weder erwähnt noch gewürdigt. Diese liessen jedoch Rückschlüsse auf den Leumund zu und seien deshalb entscheidrelevant. Der erhobene Vorwurf trifft indessen nicht zu. Das Verwaltungsgericht bezog sich zwar in der inhaltlichen Begründung seines Entscheids nicht ausdrücklich auf die angerufenen Referenzschreiben. Es äusserte sich dazu aber bei der Behandlung der bereits bei ihm erhobenen Rüge, der Regierungsrat habe den Anspruch auf rechtliches Gehör der Beschwerdeführer verletzt. Es nahm damit die fraglichen Referenzschreiben zumindest zur Kenntnis. Obwohl es diese nicht ausdrücklich würdigte, ist nicht ersichtlich, dass es sie nicht berücksichtigt hätte. Jedenfalls leiden die tatsächlichen Feststellungen des Verwaltungsgerichts insofern nicht an einem erheblichen Mangel gemäss Art. 97 Abs. 1 bzw. Art. 105 Abs. 2 BGG. Im Übrigen steht nichts entgegen, dass das Bundesgericht die Referenzschreiben bzw. den Leumund des Beschwerdeführers integral in Rechnung stellt.

2.4 Nach Art. 105 Abs. 2 BGG kann das Bundesgericht die auf einem massgeblichen Mangel beruhenden tatsächlichen Feststellungen der Vorinstanz berichtigen. Dieses Vorgehen rechtfertigt sich im vorliegenden Fall, soweit sich die Sachverhaltsfeststellungen als ungenügend erweisen, weil alle Grundlagen für eine korrekte Sachverhaltserhebung in den Akten liegen. Eine Rückweisung an die Vorinstanz zu ergänzenden Abklärungen erweist sich daher als überflüssig.

3.1 Der Regierungsrat und das Verwaltungsgericht des Kantons Zürich gingen ohne weitere Begründung davon aus, die Beschwerdeführer könnten sich auf das Freizügigkeitsrecht berufen bzw. hätten gestützt auf das Freizügigkeitsabkommen einen Anspruch auf Erteilung einer Aufenthaltsbewilligung an den Ehemann. Demgegenüber hält das Bundesamt für Migration in seiner Stellungnahme an das Bundesgericht fest, dies treffe deshalb nicht zu, weil der Beschwerdeführer sich bisher nicht rechtmässig in einem Vertragsstaat aufgehalten habe.

3.2 Nach Art. 7 lit. d FZA regelt das Freizügigkeitsabkommen unter anderem das Aufenthaltsrecht der Familienangehörigen der Staatsangehörigen der Vertragsstaaten, und zwar ungeachtet ihrer Staatsangehörigkeit. Gemäss Art. 3 Abs. 1 Anhang I FZA haben die Familienangehörigen einer Person, die Staatsangehörige einer Vertragspartei des Abkommens ist und ein Aufenthaltsrecht hat, das Recht, bei ihr Wohnung zu nehmen. Als Familienangehöriger gilt unter anderem, ungeachtet seiner Staatsangehörigkeit, der Ehegatte (vgl. Art. 3 Abs. 2 lit. a Anhang I FZA). Das Freizügigkeitsabkommen ist auch anwendbar auf EU-Bürger, die sich bereits bei dessen Inkrafttreten in der Schweiz aufhielten, wie das für die in der Schweiz niedergelassene, erwerbstätige Beschwerdeführerin zutrifft, die über die spanische Staatsangehörigkeit verfügt (vgl. BGE 130 II 1 E. 3.4 S. 7).

3.3 Nach der bisherigen Rechtsprechung des Bundesgerichts muss sich ein Drittstaatsangehöriger, der nachgezogen werden will, allerdings bereits rechtmässig mit einem nicht nur vorübergehenden Aufenthaltstitel in der Schweiz oder einem anderen Vertragsstaat aufgehalten haben (BGE 130 II 1 E. 3.6 S. 9 ff.). Diese Rechtsprechung geht auf das Urteil Akrich des Gerichtshofs der Europäischen Gemeinschaften (EuGH) vom 23. September 2003 zurück (C-109/01, Slg. 2003 I-9607), in dem vor allem über die Anwendung der Regelung der Familienvereinigung gemäss der Verordnung (EWG) Nr. 1612/68 des Rates vom 15. Oktober 1968 über die Freizügigkeit der Arbeitnehmer innerhalb der Gemeinschaft (ABl. L 257 vom 19. Oktober 1968 S. 2 ff.) zu entscheiden war. Mit dem Urteil vom 9. Januar 2007 Jia Yunying (C-1/05, Slg. 2007 I-1) relativierte der Gerichtshof seine Rechtsprechung in dem Sinne, dass die Mitgliedstaaten nicht verpflichtet seien, die mit dem Urteil Akrich geschaffene zusätzliche Voraussetzung anzuwenden, Bewilligungen an Familienangehörige mit Drittstaatsangehörigkeit also auch erteilen könnten, wenn sich diese vorher nicht bereits rechtmässig in einem Vertragsstaat aufgehalten hätten. Das Bundesgericht sah darin gemäss einem Urteil vom 30. November 2007 keine Veranlassung, seine Rechtsprechung zu ändern, insbesondere weil der EuGH die im Urteil Akrich anerkannte zusätzliche Voraussetzung der Bewilligungserteilung zwar nicht als verbindlich, aber auch nicht als unzulässig beurteilt hatte (vgl. BGE 134 II 10 E. 3 S. 14 ff.). Seither hat sich der EuGH jedoch ausdrücklich vollständig von seiner in der Sache Akrich verfolgten Rechtsauffassung abgewendet. Danach hängt das Recht auf Familiennachzug nicht mehr von einem vorherigen rechtmässigen Aufenthalt in einem Mitgliedstaat ab bzw. verletzt eine solche Voraussetzung die gemeinschaftsrechtliche Regelung der Familienvereinigung (Urteil vom 25. Juli 2008 C-127/08 Metock u.a.).

3.4 Gemäss Art. 16 Abs. 2 FZA ist für die Anwendung des Freizügigkeitsabkommens die einschlägige Rechtsprechung des EuGH vor dem Zeitpunkt der Unterzeichnung (21. Juni 1999) massgebend. Das Bundesgericht kann aber, ohne dazu verpflichtet zu sein, zum Zwecke der Auslegung des Freizügigkeitsabkommens auch seither ergangene Urteile des Gerichtshofs heranziehen (BGE 130 II 1 E. 3.6.1 S. 10 f., BGE 130 II 113  E. 5.2 S. 119 f.). Hierbei ist beachtlich, dass das Abkommen die Freizügigkeit auf der Grundlage der in der Europäischen Gemeinschaft geltenden Bestimmungen verwirklichen will (Präambel) und die Vertragsparteien zur Erreichung der Ziele des Abkommens alle erforderlichen Massnahmen treffen wollen, damit in ihren Beziehungen gleichwertige Rechte und Pflichten wie in den Rechtsakten der Europäischen Gemeinschaft, auf die Bezug genommen wird, Anwendung finden (Art. 16 Abs. 1 FZA). Das bedeutet, dass für die vom Abkommen erfassten Bereiche eine parallele Rechtslage verwirklicht werden soll (ACHERMANN/CARONI, § 6 Einfluss der völkerrechtlichen Praxis auf das schweizerische Migrationsrecht, in: Ausländerrecht, Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], 2. Aufl. 2009, Rz. 6.47; ASTRID EPINEY, Das Verbot der Diskriminierung aus Gründen der Staatsangehörigkeit, SJZ 105/2009 S. 26 f.; EPINEY/MOSTERS, Un exemple d'interprétation des accords conclus entre la Suisse et l'Union européenne: l'accord sur la libre circulation des personnes, in: Auslegung und Anwendung von Integrationsverträgen, Epiney/Rivière [Hrsg.], 2006, S. 62 ff.; LAURENT MERZ, Le droit de séjour selon l'ALCP et la jurisprudence du Tribunal fédéral, RDAF 65/2009 I S. 259). Um das Abkommensziel einer parallelen Rechtslage nicht zu gefährden, wird das Bundesgericht in angemessener Weise nach dem Stichtag (21. Juni 1999) ergangene Rechtsprechungsänderungen des EuGH in seine Beurteilung einbeziehen und ihnen Rechnung tragen. Das gilt allerdings nur, soweit das Abkommen auf gemeinschaftsrechtliche Grundsätze zurückgreift. Da der EuGH nicht berufen ist, für die Schweiz über die Auslegung des Abkommens verbindlich zu bestimmen, ist es dem Bundesgericht überdies nicht verwehrt, aus triftigen Gründen zu einer anderen Rechtsauffassung als dieser zu gelangen. Es wird dies aber mit Blick auf die angestrebte parallele Rechtslage nicht leichthin tun.

3.5 Der EuGH hielt im Entscheid Akrich fest, die Regelung der Verordnung Nr. 1612/68 beziehe sich nur auf die Freizügigkeit innerhalb der Gemeinschaft und besage nichts im Hinblick auf den Zugang zum Gemeinschaftsgebiet; der mit einem Unionsbürger verheiratete Drittstaatsangehörige müsse sich bereits rechtmässig in einem Mitgliedstaat aufhalten, wenn er das Recht geltend machen wolle, bei seinem Ehegatten, der sich in einen anderen Mitgliedstaat begibt, Wohnung zu nehmen (Urteil Akrich, a.a.O., Randnrn. 49 ff.). Aus der Sachverhaltsdarstellung und den Erwägungen geht hervor, dass Missbrauchsgesichtspunkte mit eine Rolle spielten (Urteil Akrich, a.a.O., Randnrn. 36 und 55 ff.). Das Bundesgericht übernahm diese Rechtsprechung (BGE 130 II 1), ohne allerdings gewisse Zweifel zu verhehlen. So wies es auf den Wortlaut sowohl des Freizügigkeitsabkommens als auch der Verordnung Nr. 1612/68 hin, welche eine solche Beschränkung der Familiennachzugsregelung nicht erkennen lasse (BGE 130 II 1 E. 3.6.3 S. 11 f.). Es nannte ferner einen Entscheid des EuGH (BGE 130 II 1 E. 3.6.2 S. 11), in welchem dieser noch auf anderer Grundlage argumentiert hatte und davon ausgegangen war, dass sich das Recht auf Einreise und Aufenthalt von Familienangehörigen aus Drittstaaten allein aus der familiären Beziehung ergebe (Urteil vom 25. Juli 2002 C-459/99 MRAX, Slg. 2002 I-6591 Randnrn. 59 und 80). Für das Bundesgericht blieb jedoch bedeutsam, dass Art. 3 Anhang I FZA Inhalt und Tragweite von Art. 10 der Verordnung Nr. 1612/68 übernimmt, "um die Freizügigkeit wie in der Europäischen Gemeinschaft zu realisieren" (BGE 130 II 1 E. 3.6.4 S. 12 ff.), was es nicht angezeigt erscheinen liess, das Freizügigkeitsabkommen grosszügiger zu interpretieren, als es der vom EuGH festgestellten Rechtslage innerhalb der Gemeinschaft entsprach.

3.6 Das Urteil Metock stützt sich im Unterschied zum Entscheid Akrich überwiegend auf die neue Richtlinie 2004/38/EG des Europäischen Parlaments und des Rates vom 29. April 2004 über das Recht der Unionsbürger und ihrer Familienangehörigen, sich im Hoheitsgebiet der Mitgliedstaaten frei zu bewegen und aufzuhalten (ABl. L 158 vom 30. April 2004 S. 77, bzw. in berichtigter Fassung ABl. L 229 vom 29. Juni 2004 S. 35 ff.), welche die Verordnung Nr. 1612/68 abänderte und verschiedene Richtlinien aufhob bzw. ersetzte, worunter die in Art. 5 Abs. 2 des Anhangs I zum FZA genannten Richtlinien 64/221/EWG vom 25. Februar 1964 (ABl. L 56 vom 4. April 1964 S. 850), 72/194/EWG vom 18. Mai 1972 (ABl. L 121 vom 26. Mai 1972 S. 32) und 75/35/EWG vom 17. Dezember 1974 (ABl. L 14 vom 20. Januar 1975, S. 14). Es fragt sich, ob damit eine nachträgliche Veränderung der Rechtslage eingetreten ist, die für die Schweiz nicht massgebend ist, oder ob es sich um eine Neuentwicklung der Rechtsprechung handelt, welche das Bundesgericht zur Gewährleistung der parallelen Rechtslage berücksichtigen soll.

3.6.1 Für die Auslegung des Freizügigkeitsabkommens nicht massgeblich ist grundsätzlich die nationale Umsetzung des Freizügigkeitsrechts. Insbesondere vermag es nicht den staatsvertraglichen Anspruch auf Familienvereinigung zu beeinträchtigen, dass der schweizerische Gesetzgeber neu in Art. 42 Abs. 2 AuG eine Anpassung der Nachzugsregelung für Schweizerinnen und Schweizer an diejenige des Freizügigkeitsrechts vorgenommen hat, dabei aber in Anlehnung an das Urteil Akrich als zusätzliche Voraussetzung den Besitz einer dauerhaften Aufenthaltsbewilligung in einem Staat verlangt, mit dem ein Freizügigkeitsabkommen abgeschlossen wurde. Diese Bestimmung bezweckt die Vermeidung der Inländerdiskriminierung. Zwar trifft es zu, dass mit einer Aufgabe der Akrich-Praxis für die Nachzugsrechte der Angehörigen der Europäischen Union erneut eine Benachteiligung von Schweizerinnen und Schweizern droht (vgl. MERZ, a.a.O., S. 263 ff.; MARC SPESCHA, Inländerdiskriminierung im Ausländerrecht?, AJP 2008 S. 1435 ff.; PETER UEBERSAX, § 7 Einreise und Anwesenheit, in: Ausländerrecht, Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], 2. Aufl. 2009, Rz. 7.144). Ob sich diese auf dem Weg der Rechtsprechung oder lediglich durch eine Gesetzesanpassung vermeiden lässt, braucht hier aber nicht entschieden zu werden. So oder anders bleibt die gesamte Ordnung der Familienvereinigung in sich wenig konsistent. Nach Art. 42 Abs. 1 AuG hängt der Nachzug des Ehegatten und der ledigen Kinder unter 18 Jahren von Schweizerinnen und Schweizern nicht von einem vorherigen rechtmässigen Aufenthalt in einem bestimmten Staat ab; dafür ist - im Vergleich mit Art. 3 Anhang I FZA und Art. 42 Abs. 2 AuG - nur ein beschränkter Kreis der Familienangehörigen nachzugsberechtigt, ist erforderlich, dass die Familie zusammenwohnt, und gelten die Nachzugsfristen von Art. 47 AuG sowie andere Voraussetzungen für eine Beschränkung der Familienvereinigung. Analoges gilt für den Familiennachzug von Niedergelassenen nach Art. 43 AuG bzw. altrechtlich Art. 17 Abs. 2 ANAG, was im vorliegenden Fall wesentlich ist, weil die Beschwerdeführer gestützt auf das nationale Recht über eine schwächere Rechtsstellung verfügen als gemäss dem Freizügigkeitsabkommen. Insgesamt lässt sich der schweizerischen Gesetzesordnung daher keine deutliche Leitlinie für das Verständnis der Regeln über den Familiennachzug entnehmen. Insofern kann an den Erwägungen in BGE 134 II 10 (insbes. E. 3) nicht festgehalten werden, die sich freilich einzig auf die Urteile Akrich und Yunying Jia, noch nicht aber auf das Urteil Metock bezogen. Entscheidend bleibt ohnehin, dass das Freizügigkeitsrecht auf eigener Grundlage auszulegen ist und nicht von dessen nationaler Umsetzung abhängen kann.

3.6.2 Das Urteil Metock erging nach der Unterzeichnung des Freizügigkeitsabkommens und ist für die Schweiz grundsätzlich nicht verbindlich (vgl. E. 3.4 hiervor). Das traf indessen bereits auf das Urteil Akrich zu. Das Bundesgericht schloss sich trotz einer gewissen Skepsis vor allem aus Gründen der Rechtsharmonisierung an die Akrich-Rechtsprechung an, obwohl es dazu nicht verpflichtet war. Analoge Überlegungen sprechen für eine Übernahme der angepassten Rechtsprechung. Es sind keine triftigen Gründe erkennbar, weshalb es innerhalb der Europäischen Gemeinschaft und in deren Verhältnis mit der Schweiz zwei unterschiedliche Freizügigkeitsregelungen geben sollte. Das Interesse an einer parallelen Rechtslage und mithin an einem möglichst einheitlichen Freizügigkeitsraum geht vielmehr vor. In ähnlichem Sinne hielt der Gerichtshof im Urteil Metock fest, die Verwirklichung eines Binnenmarkts und die Beseitigung der Hindernisse für den freien Personenverkehr erforderten, dass die Voraussetzungen gleich seien, unter denen Unionsbürger in andere Mitgliedstaaten, deren Staatsangehörigkeit sie nicht besitzen, einreisen und sich dort aufhalten dürften (Urteil Metock, a.a.O., Randnr. 68). Dieses Argument lässt sich analog auf das Verhältnis zwischen der Europäischen Gemeinschaft und der Schweiz übertragen. Hinzu kommt, dass die Missbrauchsaspekte, die bei der Beurteilung des Falles Akrich eine Rolle spielten, nicht verallgemeinert werden und insbesondere die Rechtsstellung derjenigen Personen nicht schmälern dürfen, die ihre Rechte nicht missbräuchlich geltend machen.

3.6.3 Gewiss hatte der EuGH bei der Beurteilung der Rechtssache Metock das in der Europäischen Union aktuell geltende Recht anzuwenden. Im hier fraglichen Zusammenhang führte die Neufassung der einschlägigen Bestimmungen jedoch zu keinen wesentlichen Änderungen. Wohl regelt die neue Richtlinie 2004/38/EG ausdrücklich die Freizügigkeitsrechte der Unionsbürger, während sich die frühere Verordnung Nr. 1612/68 auf diejenigen der Staatsangehörigen der Mitgliedstaaten bezog. Inhaltlich brachte dies aber für die hier zu entscheidende Frage der Familienvereinigung keine massgeblichen Neuerungen mit sich. Die Richtlinie 2004/38/EG fasste im Wesentlichen die bestehenden Gemeinschaftsinstrumente zur Freizügigkeit zusammen, kodifizierte die Rechtsprechung des Gerichtshofs und modifizierte die bisherige Rechtslage nur punktuell. Die Freizügigkeit und das Niederlassungsrecht der Arbeitnehmer bildeten bereits einen wesentlichen Inhalt des ursprünglichen Vertrags vom 25. März 1957 zur Gründung der Europäischen Wirtschaftsgemeinschaft (vgl. Art. 48 ff. des EWG-Vertrags in der ursprünglichen Fassung; BGBl. II Nr. 23 vom 19. August 1957 S. 766 ff.). Sie wurde im Verlauf der Jahre durch verschiedene Erlasse, worunter durch die genannten, von der Richtlinie 2004/38/EWG inzwischen abgelösten Rechtsakte, der jeweils zuständigen Organe konkretisiert, die alle - teilweise lange Zeit - vor Abschluss des Freizügigkeitsabkommens mit der Schweiz in Kraft traten. Schon früh wurde erkannt, dass für die Freizügigkeit des Staatsangehörigen eines Mitgliedstaates auch diejenige seiner Familienangehörigen bedeutsam ist (vgl. etwa das Urteil vom 7. Juli 1992 des EuGH C-370/90 Singh Slg. 1992 I-19). Die Unionsbürgerschaft wiederum wurde mit dem Vertrag von Maastricht zur Gründung der Europäischen Union vom 7. Februar 1992 (ABl. C 191 vom 29. Juli 1992 S. 1 ff.) eingeführt. Nach Art. 17 des EG-Vertrags in der konsolidierten Fassung gemäss dem Vertrag von Amsterdam vom 2. Oktober 1997 (ABl. C 340 vom 10. November 1997 S. 173) ist Unionsbürger, wer die Staatsangehörigkeit eines Mitgliedstaats besitzt. Die Unionsbürgerschaft vermittelt insbesondere das Wahl- und Petitionsrecht, den diplomatischen Schutz eines jeden Mitgliedstaates sowie die Freizügigkeitsrechte, wie sie im EG-Vertrag und in den Durchführungsvorschriften vorgesehen sind bzw. umgesetzt werden (Art. 18-21 des EG-Vertrags in der konsolidierten Fassung). Das Niederlassungsrecht wird in den Art. 43 ff. des EG-Vertrages (in der konsolidierten Fassung) lediglich in den Grundzügen geregelt; die Details finden sich in den ausführlichen Durchführungsvorschriften. Immerhin fällt auf, dass Art. 43 des EG-Vertrags (in der konsolidierten Fassung) das Recht auf freie Niederlassung nicht den Unionsbürgern, sondern gemäss der ursprünglichen Formulierung den Staatsangehörigen eines Mitgliedstaates zuerkennt. Das belegt, dass der begrifflichen Unterscheidung der Unionsbürgerschaft von den Staatsangehörigen der Mitgliedstaaten bei der Ausgestaltung der Freizügigkeitsrechte keine wesentliche Rolle zukommt. Entscheidend ist vielmehr, dass diese Rechtslage bereits vor dem 21. Juni 1999 galt.

3.6.4 Die erwähnten Zusammenhänge gehen auch aus der Rechtsprechung des EuGH hervor. Der Entscheid Metock stützt sich zwar auf die Richtlinie 2004/38/EG. Was die Rechte auf Familiennachzug betrifft, ergibt sich aus der Begriffsbestimmung der anspruchsberechtigten Familienangehörigen von Art. 2 in Verbindung mit Art. 7 Abs. 2 der Richtlinie 2004/38/EG aber auch nach Auffassung des EuGH keine relevante Änderung im Vergleich mit Art. 10 der Verordnung Nr. 1612/68, auf der die für das Verhältnis zwischen der Schweiz und den Mitgliedstaaten massgebliche Regelung von Art. 3 FZA beruht. Der Gerichtshof legte im Entscheid Metock ausdrücklich dar, dass er seine Ausführungen in der Sache Akrich auch unter dem Gesichtspunkt der damals massgebenden Regelung von Art. 10 der Verordnung Nr. 1612/68 nicht aufrechtzuerhalten vermöchte (Urteil Metock, a.a.O., Randnr. 58). Er verwies dabei auf die altrechtlichen Regelungen (Urteil Metock, a.a.O., Randnrn. 56 f.) und seine frühere Rechtsprechung (insbes. das erwähnte Urteil MRAX, a.a.O., Randnr. 59, sowie das Urteil vom 14. April 2005 C-157/03 Kommission gegen Spanien, Slg. 2005 I-2911 Randnr. 28), wonach sich das Recht auf Einreise allein aus dem Verwandtschaftsverhältnis ergebe, weshalb die Rechte aus Art. 10 der Verordnung Nr. 1612/68 des mit einem Unionsbürger verheirateten Drittstaatsangehörigen nicht davon abhängen könnten, ob er sich zuvor rechtmässig in einem anderen Mitgliedstaat aufgehalten habe (Urteil Metock, a.a.O., Randnr. 58). Daraus folgerte der EuGH, erst recht müsse die Richtlinie 2004/38/EG in gleichem Sinne ausgelegt werden, da nicht in Betracht komme, dass die Unionsbürger aus dieser Richtlinie weniger Rechte ableiten könnten als aus den Sekundärrechtsakten, die sie ändere oder aufhebe (Urteil Metock, a.a.O., Randnr. 59). Aus dieser Argumentation lässt sich klarerweise schliessen, dass für den EuGH der Gesichtspunkt der Unionsbürgerschaft bzw. deren Niederschlag in der Richtlinie 2004/38/EG lediglich ergänzend von Bedeutung war, nicht jedoch den Ausschlag gab, sondern dass der Gerichtshof auch auf der Grundlage der vorgängigen Rechtserlasse gleichermassen entschieden hätte.

3.6.5 Schliesslich wird auch im Schrifttum, soweit ersichtlich, einhellig - teils eindeutig, teils jedenfalls tendenziell - die Meinung vertreten, die schweizerische Praxis sei an die neue Rechtsprechung des EuGH im Sinne von dessen Urteil Metock anzupassen. Die entsprechenden Begründungen folgen dabei im Wesentlichen dem hier wiedergegebenen Argumentationsmuster (dazu ASTRID EPINEY, Von Akrich über Jia bis Metock: zur Anwendbarkeit der gemeinschaftlichen Regeln über den Familiennachzug - Gleichzeitig eine Anmerkung zu EuGH, Rs. C-127/08 [Metock], Urt. v. 25.7.2008, EuR6/2008, S. 840 ff.;MERZ, a.a.O., 285 ff.; SPESCHA, a.a.O., 1432 ff.; derselbe, Die familienbezogene Rechtsprechung im Migrationsrecht [ANAG/AuG/FZA/EMRK] in den Jahren 2007 und 2008 [bis Ende Juli] und zugleich ein Blick auf offene Rechtsfragen, FamPra.ch 2008S. 843 ff.).

3.7 Den Gründen für die Änderung der Rechtsprechung durch den EuGH lässt sich die Überzeugungskraft nicht absprechen. Sie tragen den Bedenken Rechnung, die das Bundesgericht bereits in BGE 130 II 1 unter Bezugnahme auf den Wortlaut und auf das Urteil i.S. MRAX angesprochen hatte. Der EuGH hält auch zu Recht fest, dass die gemeinschaftsrechtliche Regelung der Personenfreizügigkeit im Binnenmarkt gleiche Rechte gewährleisten will, unter denen sich der Freizügigkeitsberechtigte mit seiner Familie im Aufnahmemitgliedstaat niederlassen darf, was nicht zuträfe, wenn es für das Recht, die Familienangehörigen nachzuziehen, zusätzlich darauf ankäme, ob sich diese bereits rechtmässig im Gemeinschaftsgebiet aufhalten. Damit ergibt sich, dass bei der Anwendung des Freizügigkeitsabkommens zur Gewährleistung der parallelen Rechtslage in Angleichung an das Urteil Metock an der Geltung der Rechtsprechung gemäss dem Urteil Akrich nicht festgehalten werden kann. Der Nachzug eines Familienmitglieds mit Drittstaatsangehörigkeit gemäss dem Freizügigkeitsabkommen setzt demnach - in Abänderung der Rechtsprechung gemäss BGE 130 II 1 und BGE 134 II 10 - nicht voraus, dass sich dieser Familienangehörige bereits rechtmässig mit einem nicht nur vorübergehenden Aufenthaltstitel in der Schweiz oder einem anderen Vertragsstaat aufgehalten hat. Mit Blick auf die spanische Staatsangehörigkeit der Ehefrau können sich die Beschwerdeführer daher auf das Freizügigkeitsabkommen und die darin - insbesondere in Art. 3 Anhang I FZA - enthaltene Regelung des Familiennachzugs berufen.

4.1 Gemäss Art. 5 Abs. 1 Anhang I FZA dürfen die durch das Freizügigkeitsabkommen eingeräumten Rechte "nur durch Massnahmen, die aus Gründen der öffentlichen Ordnung, Sicherheit und Gesundheit gerechtfertigt sind, eingeschränkt werden". Art. 5 Abs. 2 Anhang I FZA verweist insoweit insbesondere auf die gemeinschaftsrechtliche Richtlinie 64/221/EWG, die wiederum auf den Vorbehalt der öffentlichen Ordnung, Sicherheit und Gesundheit in Art. 46 des EG-Vertrages (in der konsolidierten Fassung) zurückgeht. Diese Richtlinie bleibt trotz des Erlasses der Richtlinie 2004/38/EG für das die Schweiz betreffende Freizügigkeitsrecht massgeblich (vgl. EPINEY/MOSTERS, Die Rechtsprechung des EuGH zur Personenfreizügigkeit und ihre Implikationen für das Freizügigkeitsabkommen, in: Schweizerisches Jahrbuch für Europarecht 2007/2008, Epiney/Civitella [Hrsg.], 2008, S. 57; MERZ, a.a.O., S. 299). Eine Anpassung des Freizügigkeitsabkommens an die Richtlinie 2004/38/EG (vgl. insbes. Art. 27 ff. der Richtlinie) hat bisher nicht stattgefunden. Aber auch die Rechtsprechung des EuGH hat gestützt auf den aktuelleren Rechtsakt bis jetzt keine wesentlich neue Entwicklung im vorliegenden Zusammenhang erfahren, deren Übernahme auf das Freizügigkeitsabkommen in Frage stehen könnte.

4.2 Nach der an die Praxis des EuGH angeglichenen Rechtsprechung des Bundesgerichts setzen Entfernungs- oder Fernhaltemassnahmen eine hinreichend schwere und gegenwärtige Gefährdung der öffentlichen Ordnung durch den betreffenden Ausländer voraus. Eine strafrechtliche Verurteilung darf dabei nur insofern zum Anlass für eine derartige Massnahme genommen werden, als die ihr zugrunde liegenden Umstände ein persönliches Verhalten erkennen lassen, das eine gegenwärtige Gefährdung der öffentlichen Ordnung darstellt. Art. 5 Anhang I FZA steht somit Massnahmen entgegen, die (allein) aus generalpräventiven Gründen verfügt werden (vgl. BGE 130 II 176 E. 3.4 S. 182 ff.; BGE 129 II 215 E. 7 S. 221 ff.; je mit Hinweisen). Während die Prognose über das künftige Wohlverhalten im Rahmen der Interessenabwägung nach rein nationalem Ausländerrecht zwar mitzuberücksichtigen, aber nicht ausschlaggebend ist, kommt es bei Art. 5 Anhang I FZA wesentlich auf das Rückfallrisiko an (BGE 130 II 176 E. 4.2 S. 185 mit Hinweisen). Zu verlangen ist eine nach Art und Ausmass der möglichen Rechtsgüterverletzung zu differenzierende hinreichende Wahrscheinlichkeit, dass der Ausländer künftig die öffentliche Sicherheit und Ordnung stören wird. Je schwerer die möglichen Rechtsgüterverletzungen sind, desto niedriger sind die Anforderungen an die in Kauf zu nehmende Rückfallgefahr (BGE 130 II 176 E. 4.3.1 S. 186; vgl. auch die Urteile des Bundesgerichts 2C_624/2008 vom 15. Juni 2009 und 2C_15/2009 vom 17. Juni 2009; MERZ, a.a.O., S. 299 ff.; ZÜND/ARQUINT HILL, § 8 Beendigung der Anwesenheit, Entfernung und Fernhaltung, in: Ausländerrecht, Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], 2. Aufl. 2009, Rz. 8.38 ff.).

4.3 Der Beschwerdeführer wurde in den Jahren 1998 und 2000 zweimal insbesondere wegen Betäubungsmitteldelikten zu total 28 Monaten Freiheitsstrafe verurteilt. Diese Strafen verbüsste er weitgehend. Im November 2001 wurde er aus dem Strafvollzug entlassen. Seither wurde er einzig im März 2008 wegen eines im Jahre 2003 begangenen Vergehens gegen die Waffengesetzgebung verurteilt. Zwar trifft es zu, dass es sich bei den länger zurückliegenden Betäubungsmitteldelikten um schwerwiegende Straftaten handelte, die ein erhebliches Verschulden begründen und nicht leichtzunehmen sind. Seit seiner Haftentlassung vor acht Jahren verhielt sich der Beschwerdeführer aber weitgehend korrekt. Entgegen der Würdigung der Vorinstanz lässt sich aus dem geringen Strafmass des Strafbefehls vom März 2008 durchaus ablesen, dass das verfügende Bezirksstatthalteramt Waldenburg das Verschulden des Beschwerdeführers beim Verstoss gegen das Waffengesetz als nicht allzu schwer einstufte. Eine ausführliche Begründung dazu fehlt zwar; im Strafbefehl wird aber ausdrücklich auf die entsprechenden Bestimmungen des Strafgesetzbuches verwiesen, die eine Bestrafung nach dem Verschulden vorsehen. Auch wenn die Begründung des Beschwerdeführers, weshalb er eine Schusswaffe und diverse Munition mit sich führte, wenig überzeugend erscheint, ist ihm anzurechnen, dass sich - abgesehen vom Mitführen ohne Bewilligung - keine Hinweise auf eine unrechtmässige Verwendung finden liessen. Entscheidender ist jedoch ohnehin, dass auch das Vergehen gegen die Waffengesetzgebung nunmehr bereits rund sechs Jahre zurückliegt. Der Beschwerdeführer hat seither keine Gründe mehr gesetzt, die erkennen liessen, er könnte wieder straffällig werden. Die Rückfallgefahr ist daher nicht als erheblich einzuschätzen.

4.4 Der Beschwerdeführer verbrachte die ersten 27 Jahre seines Lebens in Palästina und hat dort noch immer etliche Verwandte und zwei Söhne. Dass er selbständig nach Palästina hätte zurückreisen können, ist nicht erstellt. Vielmehr muss davon ausgegangen werden, er sei nicht allein dafür verantwortlich, dass sich seine Ausschaffung nicht vollziehen liess (vgl. E. 2.2). Inzwischen hält sich der heute 40-jährige Beschwerdeführer seit rund 13 Jahren in der Schweiz auf. Sein Anwesenheitsstatus ist weiterhin prekär, wurde ihm bisher doch weder Asyl gewährt noch eine ausländerrechtliche Bewilligung erteilt. Das Verfahren über eine eventuelle vorläufige Aufnahme ist seit 2003 im Rechtsmittelstadium hängig. Seit zwei Jahren ist er mit seiner hier seit ihrer Kindheit lebenden und damit mit den hiesigen Verhältnissen vertrauten zweiten Frau verheiratet. Die Beziehung scheint ungetrübt zu sein. Jedenfalls setzt sich die Ehefrau für den Beschwerdeführer ein und trat bis vor Bundesgericht auch in den Rechtsmittelverfahren gegen die Bewilligungsverweigerung als Beschwerdeführerin auf. Zwar konnte die Beschwerdeführerin bei der Heirat nicht sicher sein, die Ehe in der Schweiz leben zu können; es gibt aber keine Anhaltspunkte dafür, dass dies in einem anderen Land - insbesondere in der Heimat des Beschwerdeführers und derjenigen der Ehefrau - möglich wäre. Seit seiner Haftentlassung bemüht sich der Beschwerdeführer um ein geordnetes Leben. Er lernte - anscheinend sehr gut - Deutsch und arbeitete zunächst im Gastronomiebereich und später, als ihm ein Arbeitsverbot auferlegt wurde, im Rahmen der Beschäftigungsprogramme der Asyl-Organisation Zürich. Seit Anfang 2008 ist er als Sicherheitsbeamter und Detektiv erwerbstätig. Seine Arbeitszeugnisse lauten sehr positiv. Wie die vielen Referenzschreiben belegen, ist er auch ausserhalb der Arbeitswelt recht gut integriert und jedenfalls darum bemüht, sich ein privates Beziehungsnetz aufzubauen. Im Betreibungsregister ist er nicht verzeichnet, und öffentliche Unterstützungsleistungen benötigt er nicht. All dies belegt eine kontinuierliche Stabilisierung der Lebensverhältnisse des Beschwerdeführers und spricht ebenfalls gegen eine Rückfallgefahr. Angesichts dieser Umstände besteht zurzeit keine hinreichende Wahrscheinlichkeit, dass der Beschwerdeführer künftig die öffentliche Sicherheit und Ordnung stören wird.

4.5 Sind damit die Voraussetzungen für die Beschränkung der Freizügigkeitsrechte der Beschwerdeführer gemäss Art. 5 Anhang I FZA nicht erfüllt, verstösst der angefochtene Entscheid gegen das Freizügigkeitsabkommen, insbesondere gegen Art. 7 lit. d FZA und Art. 3 Anhang I FZA.

5.1 Die Beschwerde erweist sich als begründet und ist gutzuheissen. Der angefochtene Entscheid muss aufgehoben werden, und das kantonale Migrationsamt ist anzuweisen, dem Beschwerdeführer eine Aufenthaltsbewilligung EG/EFTA zu erteilen. Die Eventualanträge werden damit gegenstandslos. Das Verwaltungsgericht wird allerdings über die Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens neu zu entscheiden haben.