2A.337/2005

{T 0/2}
2A.337/2005 /kil

Urteil vom 10. Juni 2005
II. Öffentlichrechtliche Abteilung

Besetzung
Bundesrichter Merkli, Präsident,
Bundesrichter Hungerbühler, Müller,
Gerichtsschreiber Uebersax.

Parteien
X.________,
Beschwerdeführer, vertreten durch Rechtsanwalt
Tim Walker,

gegen

Amt für Ausländerfragen Appenzell Ausserrhoden, Dorfplatz 5, Postfach 162, 9043 Trogen,
Präsident des Verwaltungsgerichts von Appenzell Ausserrhoden, 5-Eckhaus, Dorf 7, Postfach 161,
9043 Trogen.

Gegenstand
Ausschaffungshaft gemäss Art. 13b ANAG,

Verwaltungsgerichtsbeschwerde gegen den Entscheid des Präsidenten des Verwaltungsgerichts von Appenzell Ausserrhoden vom 15. April 2005.

Sachverhalt:
A.
Der angeblich aus Sierra Leone stammende X.________, geb. am ... 1985, reiste am 29. April 2004 in die Schweiz ein und stellte hier ein Asylgesuch. Am 10. Mai 2004 trat das Bundesamt für Flüchtlinge auf das Asylgesuch nicht ein und wies X.________ aus der Schweiz weg. Mit Entscheid vom 17. Mai 2004 wies die Schweizerische Asylrekurskommission eine dagegen erhobene Beschwerde ab. Danach brach der behördliche Kontakt zu X.________ ein erstes Mal ab. Nach einer polizeilichen Festhaltung und Rückführung ins Asylbewerberzentrum verschwand er zum zweiten Mal. Nachdem ihn die Polizei erneut festgenommen hatte, verfügte das Amt für Ausländerfragen des Kantons Appenzell Ausserrhoden am 11. Januar 2005 erstmals die Ausschaffungshaft. Abklärungen zu seiner Identität ergaben in der Folge, dass X.________ mit grosser Wahrscheinlichkeit aus Nigeria stammt. Weil dieses Land damals keine Personen zurücknahm, die sich nicht selbst zur nigerianischen Staatsangehörigkeit bekannten, wurde X.________ am 14. Februar 2005 aus der Ausschaffungshaft entlassen.

Nach seiner Entlassung verbüsste X.________ in Basel eine Gefängnisstrafe, die ihm wegen Verstosses gegen ausländerrechtliche Bestimmungen auferlegt worden war. Nach der Entlassung aus dem Strafvollzug wurde er dem Amt für Ausländerfragen des Kantons Appenzell Ausserrhoden zugeführt, das ihn am 12. April 2005 erneut in Ausschaffungshaft nahm. Zur Begründung führte das Amt im Wesentlichen aus, die nigerianischen Behörden hätten in Aussicht gestellt, ab Ende April 2005 wieder Anhörungen durchzuführen und Ersatzreisepapiere auszustellen; X.________ werde demnächst der nigerianischen Botschaft zur Anhörung zugeführt. Am 15. April 2005 prüfte und genehmigte der Verwaltungsgerichtspräsident von Appenzell Ausserrhoden die Ausschaffungshaft.
B.
Mit Eingabe vom 19. Mai 2005 an das Bundesgericht führt X.________ sowohl Verwaltungsgerichtsbeschwerde als auch staatsrechtliche Beschwerde. Im Wesentlichen beantragt er, der Entscheid des Verwaltungsgerichtspräsidenten sei aufzuheben und er sei aus der Ausschaffungshaft zu entlassen; eventuell sei die Ausschaffungshaft zu unterbrechen oder es sei eine mildere Ersatzmassnahme anzuordnen oder er sei in eine Asylbewerberunterkunft bzw. in ein anderes Ausschaffungsgefängnis zu verlegen. Gleichzeitig ersucht X.________ um Anordnung vorsorglicher Massnahmen, um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung sowie um persönliche Anhörung und Abhaltung einer öffentlichen mündlichen Verhandlung.

Das Amt für Ausländerfragen schliesst auf Abweisung der Beschwerden. Der Verwaltungsgerichtspräsident hat unter Hinweis auf seinen angefochtenen Entscheid auf eine Stellungnahme verzichtet. Das Bundesamt für Migration hat sich innert Frist nicht vernehmen lassen. X.________ nahm die ihm eingeräumte Gelegenheit mit zwei Eingaben vom 31. Mai und vom 8. Juni 2005 wahr, sich nochmals zur Sache zu äussern.

Das Bundesgericht zieht in Erwägung:
1.
1.1 Nach Art. 13c Abs. 2 ANAG sind die Rechtmässigkeit und die Angemessenheit der Ausschaffungshaft spätestens nach 96 Stunden durch eine richterliche Behörde aufgrund einer mündlichen Verhandlung zu überprüfen. Gegen den kantonal letztinstanzlichen Haftrichterentscheid steht die Verwaltungsgerichtsbeschwerde an das Bundesgericht offen (BGE 125 II 369 E. 2b S. 371 f. mit Hinweisen). Mit dieser kann insbesondere die Verletzung von Bundesrecht gerügt werden (Art. 104 lit. a OG), wozu auch das Bundesverfassungsrecht sowie die vom Bund abgeschlossenen Staatsverträge wie insbesondere die Europäische Menschenrechtskonvention zählen (vgl. BGE 123 II 289 E. 1c S. 291 mit Hinweis). Damit lassen sich alle vom Beschwerdeführer erhobenen Rügen im Verfahren der Verwaltungsgerichtsbeschwerde prüfen. Weil die staatsrechtliche Beschwerde nur zulässig ist, wenn die behauptete Rechtsverletzung nicht sonstwie durch Klage oder Rechtsmittel beim Bundesgericht oder einer anderen Bundesbehörde gerügt werden kann (Art. 84 Abs. 2 OG), ist auf die vom Beschwerdeführer ebenfalls erhobene staatsrechtliche Beschwerde nicht einzutreten.
1.2 Im Verfahren der Verwaltungsgerichtsbeschwerde ist das Bundesgericht an die tatsächlichen Feststellungen der Vorinstanz gebunden, wenn es sich dabei - wie hier - um eine richterliche Behörde handelt und wenn diese den Sachverhalt nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erhoben hat (Art. 105 Abs. 2 OG). Hinweise für entsprechende qualifizierte Mängel bestehen nicht. Damit ist das Bundesgericht an die tatsächlichen Feststellungen des Haftrichters gebunden, weshalb auch den ergänzenden Beweisanträgen des Beschwerdeführers nicht stattzugeben ist.
2.
Nach Art. 112 OG kann der Abteilungspräsident eine mündliche Parteiverhandlung anordnen. Eine solche ist jedoch nicht vorgeschrieben, genauso wenig wie eine persönliche Anhörung des Inhaftierten. Hingegen sieht Art. 13c Abs. 2 ANAG eine mündliche Verhandlung vor dem Haftrichter vor. Der Beschwerdeführer wurde vom Haftrichter bei der von diesem durchgeführten öffentlichen mündlichen Verhandlung persönlich angehört. Weder die Bundesverfassung noch die Europäische Menschenrechtskonvention verschaffen ihm einen Anspruch auf erneute persönliche Anhörung in einer öffentlichen mündlichen Verhandlung auch vor dem Bundesgericht als Rechtspflegeinstanz bzw. zweiter Gerichtsinstanz. Die entsprechenden Anträge des Beschwerdeführers sind damit abzuweisen.
3.
Nach der Rechtsprechung des Bundesgerichts muss über die Haftrichterverhandlung ein schriftliches Protokoll erstellt werden (BGE 125 II 377 E. 1 S. 379; Urteil 2A.607/1999 vom 6. Januar 2000, E. 1). In den Akten findet sich kein solches Protokoll. Über diesen Mangel kann jedoch ausnahmsweise hinweggesehen werden, nachdem der Beschwerdeführer das Fehlen des Protokolls nicht rügt und auch keine Sachfragen strittig sind, deren Klärung ein solches voraussetzt. Der Haftrichter wird aber ausdrücklich darauf hingewiesen, künftig diese Protokollpflicht zu beachten.
4.
4.1 Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, wenn die Voraussetzungen von Art. 13b ANAG erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt, dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist. Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (vgl. BGE 130 II 56 E. 1 S. 57 f. mit Hinweisen, 377 E. 1 S. 378 f.).
4.2 Gegen den Beschwerdeführer erging ein rechtskräftiger Wegweisungsentscheid, dessen Vollzug mangels Reisepapieren zurzeit nicht möglich ist. Sodann liegen gleich zwei Haftgründe vor:
4.2.1 Nach Art. 13b Abs. 1 lit. c ANAG kann ein Ausländer in Ausschaffungshaft genommen werden, wenn konkrete Anzeichen befürchten lassen, dass er sich der Ausschaffung entziehen will, insbesondere weil er seinen gesetzlichen Mitwirkungspflichten nicht nachkommt. Der Beschwerdeführer hat sich bisher geweigert, bei der Abklärung seiner Identität ernsthaft mitzuwirken. Er ist auch bereits zweimal untergetaucht; dabei genügt nicht, dass er angeblich immer über seinen Rechtsvertreter erreichbar gewesen wäre. Zur Sicherstellung des Wegweisungsvollzugs ist unerlässlich, dass die Behörden über seinen jeweiligen Aufenthaltsort informiert sind.
4.2.2 Gemäss Art. 13b Abs. 1 lit. d ANAG ist die Ausschaffungshaft ferner zulässig, wenn das zuständige Bundesamt einen Nichteintretensentscheid gestützt auf Art. 32 Abs. 2 lit. a-c oder Art. 33 AsylG getroffen hat. Dies ist beim Beschwerdeführer der Fall. Weitere Voraussetzungen sind grundsätzlich nicht erforderlich (vgl. BGE 130 II 377, 488). Dass vorliegend eine Ausnahmesituation gegeben wäre, ist nicht ersichtlich.
5.
5.1 Die Zulässigkeit der Haft setzt weiter die Verhältnismässigkeit derselben voraus. Überdies darf der Vollzug der Wegweisung nicht aus rechtlichen oder tatsächlichen Gründen undurchführbar sein (vgl. Art. 13c Abs. 5 lit. a ANAG). Letzteres ist in der Regel bloss der Fall, wenn die Ausschaffung auch bei gesicherter Kenntnis der Identität oder der Nationalität des Betroffenen bzw. trotz seines Mitwirkens bei der Papierbeschaffung mit grosser Wahrscheinlichkeit - etwa aufgrund einer ausdrücklichen oder zumindest klar erkennbaren und konsequent gehandhabten Weigerung des Heimatstaates, seine oder bestimmte seiner Staatsangehörigen zurückzunehmen - als ausgeschlossen erscheint. Nur falls keine oder bloss eine höchst unwahrscheinliche, rein theoretische Möglichkeit besteht, die Wegweisung zu vollziehen, ist die Haft aufzuheben, nicht indessen bei einer ernsthaften, wenn auch allenfalls (noch) geringen Aussicht hierauf (BGE 130 II 56 E. 4.1 S. 59 ff.; 127 II 168 E. 2c S. 172; Urteil 2A.312/2003 vom 17. Juli 2003, E. 2.1, betreffend Nigeria). Selbst wenn eine freiwillige Rückkehr möglich wäre, der Wegweisungsvollzug aber an der Weigerung des Ausländers, freiwillig heimzureisen, und an derjenigen seines Heimatstaates, zwangsweise Rückführungen zu dulden, scheitert, kann sich die Ausschaffungshaft als unzulässig erweisen (vgl. BGE 130 II 56 E. 4.2 S. 62 ff.; vgl. auch Peter Uebersax, Verfassungsrechtliche Fragen zur Ausschaffungshaft - eine Causerie, in: Forschungsgemeinschaft Mensch im Recht, Denise Buser/Natalie Berger/Felix Hafner/ Claudia Mund/Béatrice Speiser (Hrsg.), Menschenrechte konkret - Integration im Alltag, Basel/Genf/München 2005, S. 118 ff.).
5.2 Wegen der grossen Unwahrscheinlichkeit, die Wegweisung innert absehbarer Frist vollziehen zu können, war der Beschwerdeführer am 14. Februar 2005 aus der ersten Ausschaffungshaft entlassen worden. Inzwischen zeichnet sich nach der Feststellung des Haftrichters eine neue Zusammenarbeit mit den nigerianischen Behörden ab, die innert absehbarer Frist zu einer Vorführung des Beschwerdeführers vor der nigerianischen Botschaft führen könnte. Auch an diese tatsächliche Feststellung ist das Bundesgericht trotz der entsprechenden Zweifel des Beschwerdeführers gebunden, da keine Hinweise für einen qualifizierten Mangel nach Art. 105 Abs. 2 OG bestehen. Sollte sich die Staatsangehörigkeit von Sierra Leone erhärten, erachtet der Beschwerdeführer im Übrigen selbst eine Rückschaffung als möglich. Zurzeit kann deshalb durchaus von der ernsthaften Möglichkeit des Wegweisungsvollzugs ausgegangen werden. Die Ausschaffungshaft dient unter anderem gerade dazu, Unklarheiten über die Herkunft des Inhaftierten zu beseitigen und damit die Grundlage für die Papierbeschaffung zu legen. Sollte sich eine Anhörung des Beschwerdeführers bzw. dessen Ausschaffung nach erfolgter Anhörung - nach Nigeria oder allenfalls Sierra Leone - innert absehbarer Frist indessen als nicht realisierbar erweisen, wäre der Beschwerdeführer aus der Haft zu entlassen.
5.3 Im Übrigen erweist sich die Haftanordnung auch nicht aus anderen Gründen als unverhältnismässig. Insbesondere erscheinen die vom Beschwerdeführer beantragten Ersatzmassnahmen wie die Unterbrechung der Ausschaffungshaft, die Verlegung in eine (grundsätzlich offene) Asylbewerberunterkunft oder die Anordnung von sonstigen milderen Vorkehren wie einer regelmässigen Meldepflicht als wenig erfolgversprechend, nachdem der Beschwerdeführer bereits zweimal untergetaucht ist und noch immer nicht richtig bei der Identitätsabklärung mitwirkt. Dass er sich den Behörden nunmehr für die eigentliche zwangsweise Ausschaffung zur Verfügung halten würde, ist aufgrund seines bisherigen Verhaltens nicht ernsthaft zu erwarten.
6.
6.1 Bei der Kontrolle der Zulässigkeit der Ausschaffungshaft prüft der Haftrichter nebst anderem auch die Umstände des Haftvollzugs (vgl. Art. 13c Abs. 3 ANAG). Die Haftbedingungen (vgl. dazu insbesondere Art. 13d ANAG) bilden damit Gegenstand des haftrichterlichen Verfahrens wie auch des verwaltungsgerichtlichen Verfahrens vor dem Bundesgericht (vgl. etwa BGE 122 II 49 E. 5 S. 52 ff., 299).
6.2 Der Beschwerdeführer beantragt die Durchführung eines Augenscheins. Darauf kann im vorliegenden Fall jedoch verzichtet werden. Das Amt für Ausländerfragen bestreitet lediglich einzelne Behauptungen des Beschwerdeführers. Im Übrigen wendet es vor allem ein, ein neues Gefängnis mit speziellen Räumlichkeiten für die Ausschaffungshaft sei geplant und werde demnächst gebaut. Welchen Haftbedingungen der Beschwerdeführer ausgesetzt ist, ergibt sich sodann praktisch vollständig aus den in den Akten liegenden Unterlagen, insbesondere aus dem Bericht des Regierungsrates vom 8. März 2005 über den Neubau des Untersuchungsgefängnisses Gmünden sowie aus der zurzeit gültigen Hausordnung für das Kantonale Untersuchungsgefängnis in Trogen.
6.3 Wie das Bundesgericht bereits in BGE 122 II 299 E. 5c S. 309 festgehalten hat, muss sich ein Ausschaffungshäftling nicht entgegenhalten lassen, die Haftbedingungen in einem geplanten künftigen Ausschaffungsgefängnis erlaubten später einmal bessere Bedingungen. Selbst bei der Überprüfung einer generell-abstrakten Haftordnung muss deren verfassungskonforme Umsetzung beim konkreten Haftvollzug in einem Provisorium bis zum Eintreten der neuen Situation gewährleistet sein (vgl. BGE 123 I 221, insbes. E. II.1c/cc S. 234). Der Hinweis des Amts für Ausländerfragen auf einen neuen getrennten Zellentrakt im Untersuchungsgefängnis Gmünden für Ausschaffungshäftlinge, der frühestens im Jahre 2007 bezugsbereit sein soll, ist daher vorliegend nicht wesentlich.
6.4 Nach der gesetzlichen Regelung ist die ausländerrechtlich begründete Administrativhaft in geeigneten Räumlichkeiten zu vollziehen. Die Zusammenlegung mit Personen in Untersuchungshaft oder im Strafvollzug ist dabei zu vermeiden (so genanntes Trennungsgebot). Den Inhaftierten ist, soweit möglich, geeignete Beschäftigung anzubieten (Art. 13d Abs. 2 ANAG). Gemäss der Praxis des Bundesgerichtes wird der besonderen Situation der ausländerrechtlichen Administrativhäftlinge zwar am besten in spezifisch auf die Bedürfnisse dieser Haft eingerichteten Gebäulichkeiten Rechnung getragen. Der Vollzug von Vorbereitungs- und Ausschaffungshaft in anderen Anstalten ist jedoch nicht zum vornherein ausgeschlossen (BGE 123 I 221 E. II.1b S. 231; 122 II 49 E. 5a S. 53, 299 E. 3c S. 304). Dabei muss allerdings dem Trennungsgebot von Art. 13d Abs. 2 ANAG Nachachtung verschafft werden, und es muss für die fremdenpolizeilich Inhaftierten grundsätzlich ein liberaleres Haftregime als für Untersuchungs- oder Strafgefangene gelten (BGE 123 I 221 E. II.1b S. 231; 122 I 222 E. 2a/bb S. 226 f.). Sodann ist den Gefangenen täglich mindestens eine Stunde Spaziergang oder geeignete Bewegung im Freien zu gestatten (BGE 122 I 222 E. 4b S. 230). Von grundlegender Bedeutung ist auch der Anspruch der Häftlinge auf soziale Kontakte. Das bedeutet, dass nicht nur hinreichende Besuche durch auswärtige Personen erlaubt sein müssen, sondern dass auch die Möglichkeit sozialer Kontakte mit anderen ausländerrechtlich Inhaftierten bestehen soll. Dies setzt die regelmässige - aber nicht unbedingt dauernde - Benützbarkeit eines Gemeinschaftsraums oder zumindest die Möglichkeit gemeinschaftlicher Aktivitäten - Sport im Gefängnishof, weitere Tätigkeiten in anderen Räumen usw. - über den obligatorischen einstündigen Spaziergang hinaus voraus (BGE 122 II 299 E. 5a S. 308; vgl. zu den Anforderungen an die Haftbedingungen auch Thomas Hugi Yar, in: Uebersax/ Münch/Geiser/Arnold, Ausländerrecht, § 7 Zwangsmassnahmen im Ausländerrecht, Basel/Genf/München 2002, Rz. 7.90 ff.; Uebersax, a.a.O., S. 125 ff.).
6.5 Die Ausschaffungshaft des Beschwerdeführers wird im Untersuchungsgefängnis Trogen vollzogen, wo gemäss der geltenden Hausordnung für die Ausschaffungshäftlinge ein grundsätzlich liberaleres Regime gilt als für Untersuchungsgefangene. Der Haftrichter bezeichnet die dortigen Bedingungen dennoch als "in der Tat nicht optimal". Diese sind im Wesentlichen wie folgt zu beurteilen:
6.5.1 Das Untersuchungsgefängnis Trogen befindet sich in den obersten Geschossen des Rathauses Trogen. Einen eigenen Zellentrakt für Ausschaffungshäftlinge gibt es nicht. Diese sind aber in eigenen Zellen untergebracht und stehen in keinem direkten Kontakt zu den anderen Gefangenen, insbesondere zu den Untersuchungshäftlingen. Dem Trennungsgebot wird insofern gerade noch nachgelebt. Der Beschwerdeführer befindet sich freilich allein in seiner Zelle und hat auch keinen Kontakt zu den anderen Ausschaffungshäftlingen, was das Amt für Ausländerfragen mit dem besonders renitenten Verhalten der gegenwärtig im gleichen Gefängnis inhaftierten Ausschaffungshäftlinge begründet. Darauf kann es aber nicht ankommen. Im Ergebnis verhält es sich unbestrittenermassen so, dass der Beschwerdeführer, dem zurzeit offenbar auch keine Arbeit angeboten wird, während 23 Stunden allein in seiner Zelle eingesperrt ist. Zwar kann er eine Stunde am Tag im Gerichtshof spazieren, wobei allerdings umstritten ist, ob ihm dies auch tatsächlich, wie reglementarisch vorgeschrieben, am Wochenende ebenfalls ermöglicht wird. Auch die Zeit im Gefängnishof verbringt der Beschwerdeführer aber so oder so allein. Damit fehlt es ihm an den rechtlich erforderlichen Sozialkontakten, weshalb die ihm auferlegten Haftbedingungen schon aus diesem Grund als unzulässig beurteilt werden müssen.
6.5.2 Die Gefängnisräumlichkeiten im Rathaus Trogen wurden letztmals 1965 baulich angepasst. Der Botschaft des Regierungsrates vom 8. März 2005 zum Neubau eines Untersuchungsgefängnisses in Gmünden, die bereits dem Haftrichter vorlag, lässt sich an mehreren Stellen entnehmen, dass das Untersuchungsgefängnis Trogen in verschiedener Hinsicht die aktuellen Anforderungen an die Haftbedingungen nicht mehr erfüllt. So steht im Bericht wörtlich: Die "heute gültigen Vorgaben der Europäischen Menschenrechtskonvention (EMRK) bzw. des Bundesamtes für Justiz in Bezug auf Zellengrösse, Lichtverhältnisse, Frischluftzufuhr, Nassbereich, fehlende Brandschutzeinrichtungen, Nebenräume für Arbeit, Besuch, Einvernahmen, Arztkonsultationen, Spazierhof (nicht öffentlich einsehbar) usw. können trotzdem nicht erfüllt werden" (S. 2); "Ein Belassen der heutigen Unterbringung und Betreuungsart in Trogen entspricht wie erwähnt nicht den Vorschriften und kann daher keine Alternative sein. Bei einer allfälligen Haftungsklage oder Kontrolle - wie dies in anderen Kantonen schon geschehen ist - könnte das Gefängnis in Trogen sofort stillgelegt werden müssen" (S. 7). Diese klaren Feststellungen der kantonalen Exekutive zu den unzulässigen baulichen Haftbedingungen sprechen für sich und werden von keiner Seite widerlegt, auch wenn der Haftrichter und das Amt für Ausländerfragen die Ansicht vertreten, bis zum Bezug des Neubaus seien die heutigen Räumlichkeiten den Ausschaffungshäftlingen noch zuzumuten. Dies trifft aber gerade nicht zu (E. 6.3). Damit erweisen sich die gegenwärtigen Haftbedingungen für den Beschwerdeführer auch in baulicher Hinsicht als bundesrechtswidrig.
6.5.3 Abschliessend kann mit Blick auf die entsprechenden Rügen des Beschwerdeführers auf folgende Punkte hingewiesen werden: Ausschaffungshäftlingen steht, jedenfalls bei Bedarf, ein Recht auf grundsätzlich leichte (verträgliche) Kost zu (vgl. das Urteil des Bundesgerichts 2A.10/2002 vom 25. Januar 2002, E. 3c). Sodann muss der Aufsichts- und Betreuungsdienst für die Bedürfnisse der Ausschaffungshäftlinge ausgebildet und in geeigneter Weise organisiert sein, um mindestens einen permanenten Pikettdienst (auch an Wochenenden) in nächster Nähe des Gefängnisses zu gewährleisten und die übrigen Betreuungsaufgaben (wie die Organisation des Spaziergangs im Gefängnishof) sicherzustellen (vgl. das Urteil des Bundesgerichts 2A.506/2001 vom 10. Dezember 2001, E. 3f). Eine nähere Prüfung, ob diese Anforderungen im vorliegenden Fall erfüllt sind, was umstritten ist, kann hier jedoch unterbleiben, da die Haftbedingungen ohnehin schon aus anderen Gründen als bundesrechtswidrig beurteilt werden müssen. Offen bleiben kann schliesslich auch, ob die Handhabung der Telefonbenutzung für Ausschaffungshäftlinge im Untersuchungsgefängnis Trogen bundesrechtmässig ist (dazu BGE 122 II 299 E. 6b S. 311) bzw. ob dem Beschwerdeführer ausnahmsweise mangels sonstiger Sozialkontakte erlaubt werden muss, auf Staatskosten zu telefonieren. Das letzte Problem entfällt ohnehin, wenn die erforderlichen Sozialkontakte anderweitig gewährleistet werden.
6.6 Zusammenfassend ist festzustellen, dass die gerügten Haftbedingungen des Beschwerdeführers im Untersuchungsgefängnis Trogen den Anforderungen von Art. 13d Abs. 2 ANAG nicht genügen. Es stellt sich die Frage, welche Rechtsfolgen hieran zu knüpfen sind. Da der Richter bei der Überprüfung der Rechtmässigkeit und der Angemessenheit der Haft die Umstände des Haftvollzugs berücksichtigen muss, können ungenügende Haftbedingungen zur Haftentlassung führen. Lässt sich indessen annehmen, dass die kantonalen Behörden kurzfristig in der Lage sind, die nötigen Korrekturen vorzunehmen, kann es auch mit einer entsprechenden Anweisung sein Bewenden haben (BGE 122 II 299 E. 8a mit Hinweisen).

Es wird den kantonalen Behörden nicht möglich sein, die baulichen Unzulänglichkeiten im Untersuchungsgefängnis Trogen kurzfristig zu beseitigen. Auch die Gewährleistung der erforderlichen Sozialkontakte hängt davon ab, ob geeignete andere Ausschaffungshäftlinge inhaftiert werden, was nicht allein von den Behörden abhängt. Die allenfalls geringe Anzahl von Häftlingen erlaubt keine Abstriche an den Haftbedingungen und insbesondere an der Notwendigkeit von Sozialkontakten (vgl. das Urteil des Bundesgerichts 2A.545/2001 vom 4. Januar 2002, E. 3). In Frage kommt aber eine Verlegung des Beschwerdeführers in ein anderes Ausschaffungsgefängnis, wo die erforderlichen Haftbedingungen gewährleistet sind. Sollte es den kantonalen Behörden innert vernünftiger Frist gelingen, eine solche Verlegung - vermutlich in einen anderen Kanton - zu organisieren, fällt mit Blick darauf, dass die Ausschaffungshaft an sich zulässig ist, die sofortige Haftentlassung des Beschwerdeführers ausser Betracht. Da aber auch keine gewichtigen Sicherheitsinteressen vorliegen, rechtfertigt es sich doch, dem Kanton im vorliegenden Verfahren eine kurze Frist zur Gewährleistung der erforderlichen Haftbedingungen zu setzen, statt den Beschwerdeführer auf ein allfälliges späteres Haftverlängerungs- oder -entlassungsverfahren zu verweisen
7.
7.1 Somit ist die Verwaltungsgerichtsbeschwerde teilweise gutzuheissen. Der Entscheid des Haftrichters ist aufzuheben und die Zustimmung zur Ausschaffungshaft mit der Auflage zu erteilen, dass die Haftbedingungen sofort, spätestens aber innert Wochenfrist ab Zustellung des bundesgerichtlichen Urteils, im Sinne der Erwägungen angepasst werden. Sollte dies nicht möglich sein, wäre der Beschwerdeführer aus der Haft zu entlassen.
7.2 Da sich die Verwaltungsgerichtsbeschwerde im Wesentlichen als begründet erweist, hat der Kanton Appenzell Ausserrhoden den anwaltlich vertretenen Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 159 Abs. 1 OG); eine Gerichtsgebühr ist nicht geschuldet (Art. 156 Abs. 2 OG). Damit wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.
7.3 Mit dem Entscheid in der Sache werden die verschiedenen Anträge auf Anordnung vorsorglicher Massnahmen ebenfalls gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Auf die staatsrechtliche Beschwerde wird nicht eingetreten.
2.
2.1 Die Verwaltungsgerichtsbeschwerde wird teilweise gutgeheissen, der Entscheid des Verwaltungsgerichtspräsidenten von Appenzell Ausserrhoden vom 15. April 2005 wird aufgehoben, und die Zustimmung zur Ausschaffungshaft wird lediglich mit der Auflage erteilt, dass die Haftbedingungen spätestens innert einer Woche seit Zustellung des bundesgerichtlichen Urteils im Sinne der Erwägungen angepasst werden. Wird diese Auflage nicht eingehalten, ist der Beschwerdeführer aus der Haft zu entlassen.
2.2 Das Begehren um unverzügliche Haftentlassung wird abgewiesen.
3.
Es werden keine Kosten erhoben.
4.
Der Kanton Appenzell Ausserrhoden hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
5.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
6.
Dieses Urteil wird dem Beschwerdeführer, dem Amt für Ausländerfragen Appenzell Ausserrhoden und dem Präsident des Verwaltungsgerichts von Appenzell Ausserrhoden sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 10. Juni 2005
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: