Sachverhalt:
A. X._, türkischer Staatsangehöriger, geboren 1966, ersuchte im April 2009 darum, in die vorläufige Aufnahme seiner Ehefrau miteinbezogen zu werden. Gestützt auf eine Haftverfügung des Amtes für Migration und Personenstand des Kantons Bern vom 26. Oktober 2009 wurde er am 9. November 2009 festgenommen und in Ausschaffungshaft versetzt. Am 10. November 2009 liess er durch seinen Rechtsvertreter ein Gesuch um Erlass einer Verfügung gemäss Art. 64 Abs. 2 AuG (Wegweisung) sowie ein Gesuch um sofortige Entlassung aus der Ausschaffungshaft stellen.
B. Die Haftrichterin 7 des Haftgerichts III Bern-Mittelland trat mit Entscheid vom 11. November 2009 auf das Haftentlassungsgesuch nicht ein, weil noch keine richterliche Haftprüfung gemäss Art. 80 Abs. 2 AuG stattgefunden habe und ein Haftentlassungsgesuch gemäss Art. 80 Abs. 5 AuG frühestens einen Monat nach Haftprüfung gestellt werden könne. Das Verwaltungsgericht des Kantons Bern wies die gegen diesen Entscheid erhobene Beschwerde mit Urteil des Einzelrichters vom 12. November 2009 ab.
C. X._, der in der Folge ausgeschafft worden war, hat am 14. Dezember 2009 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten eingereicht. Er beantragt, das Urteil des Verwaltungsgerichts aufzuheben, das Verfahren zum materiellen Entscheid an das Haftgericht III Bern-Mittelland zurückzuweisen, ihm zu gestatten, sich bis zum rechtskräftigen Entscheid seines Gesuchs um Einschluss in die vorläufige Aufnahme der Ehefrau in der Schweiz aufzuhalten und in die Schweiz wieder einzureisen. Das Haftgericht III Bern-Mittelland sowie das Amt für Migration und Personenstand des Kantons Bern verzichten auf eine Vernehmlassung; das Verwaltungsgericht des Kantons Bern beantragt Nichteintreten, eventualiter Abweisung. Das Bundesamt für Migration hat keine Vernehmlassung eingereicht.
D. Mit Verfügung vom 22. Dezember 2009 hat die II. öffentlich-rechtliche Abteilung das Gesuch um unentgeltliche Rechtspflege und Verbeiständung abgewiesen.

Erwägungen:
1. 1.1 Die Beschwerde ist innert der gesetzlichen Frist (<ref-law>) eingereicht worden und richtet sich gegen den Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>).
1.2 Der Beschwerdeführer verlangt vor Bundesgericht einerseits die Überprüfung der Voraussetzungen für die Anordnung der ausländerrechtlichen Haft, andererseits Anordnungen über die Anwesenheitsberechtigung bzw. Wegweisung. In seiner Eingabe vom 10. November 2009 beantragte der Beschwerdeführer beim Haftrichter Haftentlassung. Mit Beschwerde an das Verwaltungsgericht verlangte er, das Haftgericht anzuweisen, materiell auf das Gesuch um Entlassung aus der Ausschaffungshaft einzutreten. Darauf ist der Streitgegenstand vor Bundesgericht beschränkt - worauf dieses bereits in seiner Verfügung vom 22. Dezember 2009 hingewiesen hat.
1.2 Der Beschwerdeführer verlangt vor Bundesgericht einerseits die Überprüfung der Voraussetzungen für die Anordnung der ausländerrechtlichen Haft, andererseits Anordnungen über die Anwesenheitsberechtigung bzw. Wegweisung. In seiner Eingabe vom 10. November 2009 beantragte der Beschwerdeführer beim Haftrichter Haftentlassung. Mit Beschwerde an das Verwaltungsgericht verlangte er, das Haftgericht anzuweisen, materiell auf das Gesuch um Entlassung aus der Ausschaffungshaft einzutreten. Darauf ist der Streitgegenstand vor Bundesgericht beschränkt - worauf dieses bereits in seiner Verfügung vom 22. Dezember 2009 hingewiesen hat.
1.3 1.3.1 Nach <ref-law> ist zur Beschwerde in öffentlich-rechtlichen Angelegenheiten nur legitimiert, wer u.a. ein schutzwürdiges Interesse an der Beurteilung seiner Eingabe hat (lit. c). Dieses muss nicht nur bei der Beschwerdeeinreichung, sondern auch noch im Zeitpunkt der Urteilsfällung aktuell und praktisch sein (Urteil 2C_899/2008 vom 18. Juni 2009 E. 1.2 mit Verweis auf <ref-ruling> E. 4 S. 286 f., nicht publ. in: <ref-ruling>; lediglich zum aktuellen Interesse vgl. <ref-ruling> E. 1.1 S. 103). Fällt das schutzwürdige Interesse im Laufe des Verfahrens dahin, wird die Sache als erledigt erklärt; fehlte es schon bei der Beschwerdeeinreichung, ist auf die Eingabe nicht einzutreten (Urteil 2C_899/2008 vom 18. Juni 2009 E. 1.2 mit Verweis auf <ref-ruling> E. 2 S. 7, nicht publ. in: <ref-ruling>; vgl. auch <ref-ruling> E. 1.1 S. 103). Das Bundesgericht verzichtet ausnahmsweise auf das Erfordernis des aktuellen praktischen Interesses, wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen deren grundsätzlicher Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1.1 S. 103; <ref-ruling> E. 1.1 S. 81).
1.3.2 Der Beschwerdeführer wurde am 9. November 2009 festgenommen und in Ausschaffungshaft versetzt. Am 10. November 2009 stellte er ein Haftentlassungsgesuch. Der Beschwerdeführer befindet sich mittlerweile im Ausland und verfügt über kein aktuelles praktisches Interesse mehr. Im vorliegenden Fall verzichtet das Bundesgericht indes - allerdings nur in Bezug auf das Haftentlassungsgesuch und nicht in Bezug auf die Anordnung der Haft und deren Voraussetzungen - auf dieses: Der Beschwerdeführer hat von sich aus ein Haftprüfungsverfahren beantragt und damit die Frage des Zusammenspiels des Art. 80 Abs. 2 des Bundesgesetzes über die Ausländerinnen und Ausländer vom 16. Dezember 2005 (AuG; SR 142.20) sowie der <ref-law> und Art. 5 Ziff. 4 EMRK (SR 0.101) aufgeworfen, welche sich immer wieder stellt, aber kaum überprüft werden kann. Es handelt sich zudem um eine grundsätzliche Frage.
1.4 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254). Der Grundsatz der Rechtsanwendung von Amtes wegen gilt nicht, soweit eine Verletzung von Grundrechten sowie von kantonalem und interkantonalem Recht geltend gemacht wird (vgl. <ref-law>). In diesem Fall müssen die Beschwerdeführer in ihrer Eingabe präzise und in Auseinandersetzung mit den Ausführungen der Vorinstanz im Einzelnen darlegen, inwiefern der angefochtene Entscheid widerrechtlich sein soll ("qualifizierte Rügepflicht"; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 1.4 S. 287). Das Bundesgericht legt seinem Urteil zudem den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>).
2. 2.1 Der Beschwerdeführer hat am 10. November 2009 vor dem Haftgericht III Bern-Mittelland beantragt, ihn aus der Ausschaffungshaft, welche am 9. November 2009 begonnen hat, zu entlassen. Sowohl das Haftgericht als auch das Verwaltungsgericht des Kantons Bern prüften dieses Begehren unter dem Titel einerseits von Art. 80 Abs. 5 AuG, andererseits von Art. 80 Abs. 2 AuG. Das Haftgericht trat auf das Gesuch nicht ein, das Verwaltungsgericht wies die dagegen gerichtete Beschwerde ab.
2.2 Nach Art. 80 Abs. 5 AuG kann eine inhaftierte Person erst einen Monat nach der Haftüberprüfung ein Haftentlassungsgesuch einreichen. Offensichtlich ist, dass im Zeitpunkt als der Beschwerdeführer sein Gesuch um Haftentlassung einreichte, noch keine erstmalige Haftüberprüfung im Sinne von Art. 80 Abs. 2 AuG erfolgt war. Insofern kann das Gesuch um Haftentlassung nur so verstanden werden, dass der Beschwerdeführer von sich aus eine erstmalige Haftüberprüfung beantragt hatte. Wäre die Haft in diesem Fall unrechtmässig gewesen, wäre der Beschwerdeführer aus der Haft zu entlassen gewesen. Indem die Vorinstanzen die vom Beschwerdeführer verwendete Wortwahl "Haftentlassung" nur auf den Begriff der Haftentlassung nach Art. 80 Abs. 5 AuG beziehen, verstehen sie die Worte des Gesuchs viel zu restriktiv bzw. zu formalisiert, anstatt von deren Sinn auszugehen. Die zu prüfende Frage wäre gewesen, ob und wie sich der Antrag des Beschwerdeführers mit Art. 80 Abs. 2 AuG vereinbaren lässt.
2.2 Nach Art. 80 Abs. 5 AuG kann eine inhaftierte Person erst einen Monat nach der Haftüberprüfung ein Haftentlassungsgesuch einreichen. Offensichtlich ist, dass im Zeitpunkt als der Beschwerdeführer sein Gesuch um Haftentlassung einreichte, noch keine erstmalige Haftüberprüfung im Sinne von Art. 80 Abs. 2 AuG erfolgt war. Insofern kann das Gesuch um Haftentlassung nur so verstanden werden, dass der Beschwerdeführer von sich aus eine erstmalige Haftüberprüfung beantragt hatte. Wäre die Haft in diesem Fall unrechtmässig gewesen, wäre der Beschwerdeführer aus der Haft zu entlassen gewesen. Indem die Vorinstanzen die vom Beschwerdeführer verwendete Wortwahl "Haftentlassung" nur auf den Begriff der Haftentlassung nach Art. 80 Abs. 5 AuG beziehen, verstehen sie die Worte des Gesuchs viel zu restriktiv bzw. zu formalisiert, anstatt von deren Sinn auszugehen. Die zu prüfende Frage wäre gewesen, ob und wie sich der Antrag des Beschwerdeführers mit Art. 80 Abs. 2 AuG vereinbaren lässt.
2.3 2.3.1 In Bezug auf Art. 80 Abs. 2 AuG hat das Haftgericht festgehalten, dass dem Haftrichter kein Antrag zur Überprüfung der Haft vorliege und die Fremdenpolizei einen Ausländer grundsätzlich während 96 Stunden ohne richterliche Prüfung festhalten könne. Es könne deshalb nicht über den Umweg eines Haftentlassungsgesuchs im Sinne von Art. 80 Abs. 5 AuG verlangt werden, dass das Gericht vor Ablauf der 96 Stunden die Rechtmässigkeit und Angemessenheit der Ausschaffungshaft prüfe, weshalb auf das Begehren nicht einzutreten sei.
2.3.2 Der Beschwerdeführer bringt dagegen vor, dass er aufgrund von <ref-law> und Art. 5 Ziff. 4 EMRK jederzeit ein Gericht anrufen könne, welches möglichst rasch zu entscheiden habe; durch den Entscheid des Haftrichters und des Verwaltungsgerichts werde ihm dieses Recht verweigert.
2.3.2 Der Beschwerdeführer bringt dagegen vor, dass er aufgrund von <ref-law> und Art. 5 Ziff. 4 EMRK jederzeit ein Gericht anrufen könne, welches möglichst rasch zu entscheiden habe; durch den Entscheid des Haftrichters und des Verwaltungsgerichts werde ihm dieses Recht verweigert.
2.4 2.4.1 Nach Art. 5 Ziff. 4 EMRK hat jede Person, die festgenommen oder der die Freiheit entzogen ist, das Recht zu beantragen, dass ein Gericht innerhalb kurzer Frist über die Rechtmässigkeit des Freiheitsentzugs entscheidet und ihre Entlassung anordnet, wenn der Freiheitsentzug nicht rechtmässig ist. Nach <ref-law> hat jede Person, der die Freiheit nicht von einem Gericht entzogen wird, das Recht, jederzeit ein Gericht anzurufen. Dieses entscheidet so rasch wie möglich über die Rechtmässigkeit des Freiheitsentzugs.
2.4.2 Nach der Rechtsprechung des Bundesgerichts beschränkt sich die Bestimmung von <ref-law> nicht wie Art. 5 Ziff. 4 EMRK darauf, auf einen Antrag hin so rasch als möglich, allenfalls nach Prüfung durch eine Verwaltungsbehörde, eine gerichtliche Beurteilung des Freiheitsentzuges zu gewährleisten. Vielmehr räumt sie jeder von einem Freiheitsentzug betroffenen Person das Recht ein, "jederzeit ein Gericht anzurufen", damit dieses so rasch als möglich über die Rechtmässigkeit des Freiheitsentzuges befinde. Die Bestimmung von <ref-law> ist in dem Sinne zu verstehen, dass der Richter jederzeit und somit direkt soll angerufen werden können und nicht bloss auf indirektem Weg. Die Norm stellt eine besondere Rechtsweggarantie dar, welche weiter reicht als die allgemeine Garantie von <ref-law>. Sie bedeutet, dass der gerichtliche Rechtsschutz gegen den Freiheitsentzug bzw. die Aufrechterhaltung der Freiheitsentziehung unmittelbar einsetzt. Damit erfährt der gerichtliche Rechtsschutz eine Stärkung. Das angerufene Gericht wird unmittelbar in die Lage versetzt, den Freiheitsentzug einer Prüfung zu unterziehen und allenfalls schon im Voraus vorsorgliche Massnahmen zu treffen (<ref-ruling> E. 6.5.2 S. 107 f.). "Jederzeit ein Gericht anzurufen" erlaubt somit denjenigen Personen, denen die Freiheit entzogen wurde, den Zeitpunkt der Anrufung des Richters selbst zu bestimmen. Jederzeit kann somit auch heissen, dass der Betroffene sofort nach dem Freiheitsentzug an die richterliche Behörde gelangt und sein Gesuch dadurch die amtliche Überweisung der Sache an den Richter zeitlich überholt.
2.4.3 Den Zeitpunkt der Anrufung des Richters selber zu bestimmen, heisst allerdings noch nicht, dass damit auch die Überprüfung der Haft durch den Verhafteten unmittelbar bestimmt wird. Nach <ref-law> entscheidet das Gericht "so rasch wie möglich" und nach Art. 5 Ziff. 4 EMRK "innerhalb kurzer Frist" (dazu auch Botschaft über eine neue Bundesverfassung vom 20. November 1996, BBl 1997 I 1 ff., 186). Welche Zeitdauer als so rasch als möglich bzw. als innerhalb kurzer Frist gilt, innerhalb derer ein Haftüberprüfungsverfahren durchgeführt werden muss, hängt von den Umständen des konkreten Einzelfalles ab, insbesondere der Art der Haft und ihrer Gründe sowie der Komplexität des Verfahrens (vgl. JÖRG PAUL MÜLLER/MARKUS SCHEFER, Grundrechte in der Schweiz, 4. Aufl. 2008, S. 109). Durch die Möglichkeit, eine Haft früher ihrer Überprüfung zuführen zu können, folgt deshalb nicht notwendigerweise, dass auch der Richter früher zu einem Entscheid kommen muss. Allerdings darf durch das Verhalten des Richters der grundrechtliche Anspruch auf jederzeitige Anrufung eines Gerichts zur Überprüfung der Haft nicht ausgehöhlt werden (siehe dazu auch REGINA KIENER/WALTER KÄLIN, Grundrechte, 2007, S. 66), indem der Richter etwa so lange zuwartet, bis die Angelegenheit gegenstandslos wird: Grundrechte sind - worauf <ref-law> verweist - in der Rechtsordnung zu verwirklichen, sei es im Rahmen der Gesetzgebung, sei es im Rahmen der Rechtsanwendung. Insofern enthält <ref-law> eine spezielle Vorschrift des Verbots der Rechtsverweigerung im engeren Sinn (vgl. auch <ref-law>).
2.4.4 Art. 80 Abs. 2 AuG verlangt, dass innert einer Frist von 96 Stunden der Richter über die Rechtmässigkeit und Angemessenheit der angeordneten Haft entscheidet. Danach kann die kantonale Behörde einen Ausländer bei Vorliegen der entsprechenden Voraussetzungen während 96 Stunden ohne richterliche Prüfung festhalten, wenn sie aufgrund der konkreten Umstände davon ausgehen darf, dass der Vollzug der Wegweisung innert dieser Frist möglich sein wird (vgl. Urteil 2A.367/2003 vom 26. August 2003 E. 2.2). Kommt die kantonale Behörde kurz vor Ablauf der 96 Stunden zum Schluss, dass der Vollzug der Wegweisung innert der Frist nicht möglich sein wird, kann sie immer noch eine Haftüberprüfung in die Wege leiten. Sie hat dabei allerdings zu berücksichtigen, dass der Richter eine mündliche Verhandlung durchzuführen und innert 96 Stunden seit der Haftanordnung zu entscheiden hat (Art. 80 Abs. 2 AuG). Nach der Rechtsprechung (vgl. <ref-ruling> E. 2b S. 371 f.) und Lehre (vgl. THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Uebersax/Rudin/Hugi Yar/Geiser, Ausländerrecht, 2009, S. 417 ff., N. 10.19) genügt dies den Mindestanforderungen von Art. 5 Ziff. 4 EMRK.
Im Hinblick auf die vorliegende Streitsache stellt sich nunmehr die Frage, ob diese Regelung auch den Anforderungen von <ref-law> und auch von Art. 5 Ziff. 4 EMRK, sofern der Gesuchsteller selbst ein Gesuch auf Haftprüfung stellt, entspricht. Dabei ist zu berücksichtigen, dass das AuG ein Bundesgesetz ist, welches - im Sinne eines Anwendungsgebots und keines Prüfungsverbots (<ref-ruling> E. 3.1 S. 391) - für das Bundesgericht massgebend ist (<ref-law>).
2.4.5 Art. 80 Abs. 2 AuG hat die ausländerrechtlich zuständige Behörde und nicht den verhafteten Ausländer im Blick. Er verpflichtet jene, innert 96 Stunden die Haftprüfung zu veranlassen. Adressat sind die ausländerrechtlichen Vollzugsorgane. Insofern handelt es sich um eine obligatorische - gesetzlich angeordnete - richterliche Haftüberprüfung (vgl. dazu HUGI YAR, a.a.O., N. 10.19). Zur Sicherung der Grundrechte der in der Regel rechtsunkundigen Ausländer sollen diese von Amtes wegen in den Genuss der Ansprüche des Art. 5 Ziff. 4 EMRK kommen. Art. 80 Abs. 2 AuG ist insofern mit dem Inhalt von <ref-law> vergleichbar, der für Personen in Untersuchungshaft gilt und ebenfalls eine obligatorische Haftüberprüfung vorschreibt (dazu MÜLLER/SCHEFER, a.a.O., S. 101). <ref-law> - und im Übrigen auch Art. 5 Ziff. 4 EMRK - hat demgegenüber den verhafteten Ausländer im Blick, der selbständig seine Haft einer Überprüfung zuführen will. Insofern sind die beiden Konstellationen nicht vergleichbar. Art. 80 Abs. 2 AuG umfasst daher - und auch unter Berücksichtigung eines fehlenden qualifizierten Schweigens (dazu <ref-ruling> E. 2.1 S. 386) - nicht die zu beurteilende Situation. Er bildet somit keinen Hinderungsgrund (<ref-law>), den Gehalt von <ref-law> und auch von Art. 5 Ziff. 4 EMRK vorliegendenfalls zur Anwendung zu bringen.
2.5 In der hier strittigen Angelegenheit hat der Beschwerdeführer kurz nach seiner Festnahme beim Haftgericht III Bern-Mittelland ein Gesuch um Haftüberprüfung gestellt. Entsprechend den Ausführungen (oben E. 2.4) wäre der Richter verpflichtet gewesen, das Gesuch entgegenzunehmen und die Haftüberprüfung in die Wege zu leiten, indem die zuständige kantonale Behörde unter Fristansetzung aufgefordert worden wäre, die notwendigen Unterlagen dem Gericht einzureichen. Durch die Nichtanhandnahme des Gesuchs hat der Haftrichter dem Beschwerdeführer das Recht aus <ref-law> und aus Art. 5 Ziff. 4 EMRK verweigert (siehe auch <ref-law>). Die Argumentation sowohl des Haftgerichts III Bern-Mittelland als auch des Verwaltungsgerichts verkennt den grundrechtlichen Gehalt des Gesuchs des Beschwerdeführers. Wie bereits ausgeführt, wollen <ref-law> und Art. 80 Abs. 2 AuG zwei unterschiedliche Konstellationen regeln: hier die Überprüfung von Amtes wegen, dort die durch den Beschwerdeführer ausgelöste Haftüberprüfung. Was in diesem Zusammenhang schliesslich "so rasch als möglich" (<ref-law>) heisst, braucht nicht abschliessend beurteilt zu werden. In jedem Fall war es unzulässig, auf das Gesuch um Haftentlassung nicht einzutreten. Unzulässig wäre es auch gewesen, das Gesuch in der Annahme, die Ausschaffung könne innert 96 Stunden erfolgen, ruhen zu lassen. Vielmehr hätte es entgegengenommen und beförderlich der Entscheidung zugeführt werden sollen.
3. 3.1 Die Beschwerde erweist sich damit als begründet und ist gutzuheissen.
3.2 Bei diesem Verfahrensausgang sind keine Kosten zu erheben (<ref-law>). Hingegen hat der Kanton Bern den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (68 Abs. 1 BGG). Das Verwaltungsgericht des Kantons Bern wird über die kantonale Kosten- und Entschädigungsregelung neu zu befinden haben (Art. 67 e contrario und 68 Abs. 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und das Urteil des Verwaltungsgerichts des Kantons Bern vom 12. November 2009 aufgehoben.
2. Es wird festgestellt, dass das Haftgericht III Bern-Mittelland zu Unrecht auf das Haftentlassungsgesuch vom 10. November 2009 nicht eingetreten ist.
3. Es werden keine Kosten erhoben.
4. Der Kanton Bern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2000.-- zu entschädigen.
5. Zur Regelung der Kosten- und Entschädigungsfolge des kantonalen Verfahrens wird die Sache an das Verwaltungsgericht des Kantons Bern zurückgewiesen.
6. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Bern und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 19. Oktober 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Errass