Sachverhalt:
A.
A._ (geb. 27. Januar 1992, Staatsangehöriger von Sri Lanka) reiste am 5. Oktober 2015 in die Schweiz ein und stellte gleichentags ein Asylgesuch. Das Staatssekretariat für Migration (SEM) wies das Gesuch mit Verfügung vom 21. August 2017 ab und wies ihn aus der Schweiz weg. Mit Urteil vom 2. November 2017 wies das Bundesverwaltungsgericht eine gegen die Verfügung vom 21. August 2017 erhobene Beschwerde ab. Das SEM setzte A._ daraufhin eine Frist bis 7. Dezember 2017 zur Ausreise an. Anlässlich eines Ausreisegesprächs vom 23. November 2017 führte A._ aus, er sei nicht bereit, die Schweiz zu verlassen. Gleichzeitig nahm er zur Kenntnis, dass er nach unbenütztem Ablauf der Ausreisefrist mit ausländerrechtlichen Zwangsmassnahmen rechnen müsse.
B.
Das Departement Inneres und Sicherheit (Amt für Inneres, Abteilung Migration) des Kantons Appenzell Ausserrhoden (fortan: Abteilung Migration) liess A._ am 29. Januar 2018 festnehmen und beantragte mit Eingabe vom 30. Januar 2018 beim Obergericht des Kantons Appenzell Ausserrhoden die Bestätigung der Ausschaffungshaft bis 31. März 2018.
Am 2. Februar 2018 teilte A._ dem Obergericht mit, dass er bereits am 30. Januar 2018 dem SEM ein neues Asylgesuch eingereicht habe. Gleichzeitig verlangte er seine sofortige Haftentlassung. Nach entsprechenden Abklärungen gegenüber dem SEM wurde A._ auf Anordnung der Abteilung Migration gleichentags aus der Haft entlassen.
Mit Entscheid vom 2. Februar 2018 schrieb das Obergericht das Verfahren wegen Gegenstandslosigkeit ab und verfügte, dass über die Kosten des Verfahrens später entschieden werde. Nach Durchführung eines Schriftenwechsels verzichtete das Obergericht mit Entscheid vom 12. März 2018 auf die Erhebung von Kosten (Ziff. 1 im Dispositiv), sprach A._ keine Parteientschädigung zu (Ziff. 2 im Dispositiv) und wies das Begehren um Haftentschädigung ab (Ziff. 3im Dispositiv).
C.
Gegen den Entscheid vom 12. März 2018 gelangt A._ mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. April 2018 an das Bundesgericht. Er beantragt Ziff. 2 im Dispositiv des angefochtenen Urteils aufzuheben und ihm eine Parteientschädigung für das vorinstanzliche Verfahren von Fr. 1'000.-- zuzusprechen. Weiter verlangt er die Aufhebung von Ziff. 3 im Dispositiv des angefochtenen Urteils und die Ausrichtung einer angemessenen Haftentschädigung. Für das bundesgerichtliche Verfahren beantragt er die Gewährung der unentgeltlichen Rechtspflege unter Beigabe von Rechtsanwalt Gabriel Püntener als unentgeltlicher Rechtsbeistand.
Die Abteilung Migration verzichtet auf eine Vernehmlassung. Das Obergericht beantragt die Abweisung der Beschwerde.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit und die weiteren Eintretensvoraussetzungen von Amtes wegen (Art. 29 Abs. 1 BGG) und mit freier Kognition (<ref-ruling> E. 1 S. 116).
1.1. Die, unter Vorbehalt einer in allen Teilen rechtsgenüglichen Begründung, form- und fristgerecht eingereichte Beschwerde richtet sich gegen den kantonal letztinstanzlichen, verfahrensabschliessenden Entscheid eines oberen Gerichts in einer Angelegenheit des öffentlichen Rechts (Art. 42 Abs. 1 und Abs. 2, Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 90 und Art. 100 Abs. 1 BGG). Nach dem Grundsatz der Einheit des Verfahrens (vgl. <ref-ruling> E. 1.3 S. 428; <ref-ruling> E. 1.1 S. 503) richtet sich die Zulässigkeit des Rechtsmittels nach dem in der Sache betroffenen Rechtsverhältnis. Hier betraf das Ausgangsverfahren die Anordnung ausländerrechtlicher Administrativhaft. Diesbezüglich greift kein Ausnahmegrund nach Art. 83 BGG (vgl. <ref-ruling> E. 1.1.3 mit Hinweisen), sodass sich die ordentliche Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den angefochtenen Entscheid als zulässig erweist. In Bezug auf die Partei- und Haftentschädigung ist der Beschwerdeführer auch nach seiner Entlassung aus der Haft im Sinne von Art. 89 Abs. 1 BGG zur Beschwerde legitimiert. Auf die Beschwerde ist grundsätzlich einzutreten.
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann namentlich die Verletzung von Bundes- und Völkerrecht gerügt werden (Art. 95 lit. a und lit. b BGG). Die richtige Anwendung kantonalen Rechts prüft das Bundesgericht abgesehen von den hier nicht einschlägigen Art. 95 lit. c-e BGG nicht als solche, sondern nur auf ihre Vereinbarkeit mit Bundes- und Völkerrecht hin. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 2 BGG), grundsätzlich nur die geltend gemachten Vorbringen, sofern allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (vgl. <ref-ruling> E. 1.6 S. 280 f.; <ref-ruling> E. 1.4.1 S. 254). Die Verletzung von Grundrechten untersucht das Bundesgericht in jedem Fall nur insoweit, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; <ref-ruling> E. 3 S. 415; <ref-ruling> E. 1.4.2 S. 254).
1.3. Seinem Urteil legt das Bundesgericht den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Eine Berichtigung der vorinstanzlichen Sachverhaltsfeststellungen ist von Amtes wegen (Art. 105 Abs. 2 BGG) oder auf Rüge hin (Art. 97 Abs. 1 BGG) möglich. Im bundesgerichtlichen Verfahren dürfen neue Tatsachen und Beweismittel nur so weit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Zu Tatsachen oder Beweismitteln, die sich erst nach dem angefochtenen Entscheid ereignet haben oder entstanden sind, kann dieser von vornherein nicht Anlass gegeben haben. Im bundesgerichtlichen Verfahren bleiben sie daher unbeachtlich (vgl. <ref-ruling> E. 3.1.2 S. 123; <ref-ruling> E. 2.1 S. 344; Urteil 2C_347 / 2C_357/2012 vom 28. März 2013 E. 2.5 [nicht publ. in: <ref-ruling>]).
Mit seiner Eingabe reicht der Beschwerdeführer einen Arztbericht ein, der vom 20. März 2018 datiert. Dabei handelt es sich nach dem soeben Dargelegten um ein Beweismittel, das im bundesgerichtlichen Verfahren nicht berücksichtigt werden kann.
2.
Der Beschwerdeführer beantragt Ziff. 2 im Dispositiv des angefochtenen Entscheids aufzuheben und ihm eine Parteientschädigung für das vorinstanzliche Verfahren zuzusprechen (vgl. E. 2.1 hiernach). Weiter verlangt er die Ausrichtung einer Haftentschädigung (vgl. E. 2.2 hiernach).
2.1. Das Obergericht erwog, dass die obsiegende Partei nach Art. 53 Abs. 3 des Gesetzes des Kantons Appenzell Auserrhoden vom 9. September 2002 über die Verwaltungsrechtspflege (Verwaltungsrechtspflegegesetz, VRPG; bGS 143.1) in der Regel Anspruch auf eine Entschädigung für ihre notwendigen Kosten und Auslagen habe. Nach Art. 59 Abs. 1 i.V.m. Art. 24 Abs. 3 lit. b VRPG keine Entschädigung ausgerichtet werde, wenn die Voraussetzungen des Obsiegens erst im Rechtsmittelverfahren geschaffen wurden. Der Beschwerdeführer sei zwar während des hängigen Verfahrens von der Abteilung Migration aus der Haft entlassen worden. Zurückzuführen sei dies jedoch auf ein neu eingereichtes Asylgesuch. Damit habe der Beschwerdeführer neue Gegebenheiten geschaffen (Art. 59 i.V.m. Art. 24 Abs. 3 lit. b VRPG), sodass er nicht als obsiegend im Sinne von Art. 53 Abs. 3 VRPG gelten könne.
2.1.1. In seiner Eingabe an das Bundesgericht beschränkt sich der Beschwerdeführer weitgehend auf Ausführungen zu seiner gesundheitlichen Situation und macht geltend, dass diese im Rahmen des neuen Asylverfahrens langwierige Abklärungen nach sich ziehen würden. Dieser Umstand schliesst nach Auffassung des Beschwerdeführers aus, dass über sein Asylgesuch innert baldiger Frist entschieden werden könne. Angesichts dessen sei es "nicht haltbar", ihm in analoger Anwendung von Art. 24 Abs. 3 lit. b VRPG eine Parteientschädigung zu verweigern.
2.1.2. Der Beschwerdeführer nennt keine konkrete Norm im Sinne von Art. 95 BGG, gegen die das Obergericht mit seiner Auslegung und Anwendung des kantonalen Verwaltungsrechtspflegegesetzes verstossen haben soll. Soweit er das Vorgehen der Vorinstanz als unhaltbar bezeichnet, rügt er zwar sinngemäss eine Verletzung des Willkürverbots gemäss Art. 9 BV (vgl. <ref-ruling> E. 4.3 mit Hinweisen). Er legt aber nicht konkret dar, inwiefern der Verzicht auf die Ausrichtung einer Parteientschädigung mit Rücksicht auf die kantonalen Rechtsgrundlagen im Ergebnis geradezu willkürlich sein soll. Soweit seine Ausführungen den gesteigerten Anforderungen gemäss Art. 106 Abs. 2 BGG überhaupt genügen, sind sie jedenfalls nicht geeignet, eine bundes- oder völkerrechtswidrige Kostenverteilung durch das Obergericht darzutun. Damit ist die Beschwerde in Bezug auf Antrag Ziff. 1 abzuweisen, soweit darauf eingetreten werden kann.
2.2. Mit Blick auf den Zeitpunkt der Haftbeendigung erwog das Obergericht, dass die blosse Einreichung eines Asylgesuchs noch nicht zur Folge habe, dass eine Person unverzüglich aus der Ausschaffungshaft zu entlassen sei. Wann genau die Abteilung Migration über das Asylgesuch vom 30. Januar 2018 im Bilde gewesen sei, bleibe unklar. Zudem habe der Beschwerdeführer erst vor Kurzem ein Asylverfahren durchlaufen und seiner Beschwerde an das Bundesverwaltungsgericht gegen den abschlägigen Asylentscheid des SEM sei kein Erfolg beschieden gewesen. Mit einem baldigen Entscheid über das neue Asylgesuch habe folglich gerechnet werden können, sodass die Aufrechterhaltung der Haft jedenfalls bis zum Moment der Entlassung des Beschwerdeführers rechtmässig gewesen sei.
2.2.1. Der Beschwerdeführer wendet dagegen ein, dass mit einer baldigen Entscheidung über das neue Asylgesuch mitnichten gerechnet werden könne. In seinem neuen Gesuch weise er an mehreren Stellen auf die Vermutung einer schweren psychischen Störung und die Notwendigkeit eines ärztlichen Gutachtens hin. Im ersten Asylverfahren sei das beobachtete Krankheitsbild des Beschwerdeführers komplett ignoriert worden. Angesichts dessen sei mit langwierigen Abklärungen zu rechnen. Nach Auffassung des Beschwerdeführers hätte er daher sogleich nach Einreichung des neuen Asylgesuchs vom 30. Januar 2018 aus der Haft entlassen werden müssen und nicht erst am 2. Februar 2018.
2.2.2. Die Vorinstanz hat zutreffend darauf hingewiesen, dass die Fortsetzung der Ausschaffungshaft auch bei Einreichung eines Asylgesuchs zulässig ist, sofern mit dem Abschluss des Asylverfahrens und dem Vollzug der Wegweisung in absehbarer Zeit gerechnet werden kann (vgl. <ref-ruling> E. 2.3.3 S. 413; <ref-ruling> E. 2b S. 380; Urteile 2C_268/2018 vom 11. April 2018 E. 2.1.1; 2C_260/2018 vom 9. April 2018 E. 4.2). Ob das der Fall ist, hat die zuständige Behörde mit Blick auf den Grundsatz der Verhältnismässigkeit (Art. 5 Abs. 2 und Art. 36 Abs. 3 BV; <ref-ruling> E. 4.1 S. 150 f.; <ref-ruling> E. 3.1 S. 380 f.) umgehend zu prüfen, wobei gegebenenfalls mit dem für die Beurteilung des Asylgesuchs zuständigen SEM Rücksprache zu nehmen ist.
2.2.3. Was der Beschwerdeführer im bundesgerichtlichen Verfahren vorbringt lässt den Schluss nicht zu, dass seine Entlassung aus der Haft in Anbetracht der konkreten Umstände verspätet erfolgte. Eine Beschwerde gegen ein erstes Asylgesuch vom 5. Oktober 2015 hatte das Bundesverwaltungsgericht mit Urteil vom 2. November 2017 abgewiesen. Die Abteilung Migration konnte daher grundsätzlich davon ausgehen, dass über ein neues Asylgesuch mit baldigem Entscheid befunden werden kann und die beantragte Ausschaffungshaft weiterhin zulässig ist. Daran ändern auch die vom Beschwerdeführer nach eigenen Angaben erst nach dem Urteil vom 2. November 2017 entdeckten gesundheitlichen Probleme nichts, zumal es sich dabei nicht ohne Weiteres um Umstände handelt, die auf eine offensichtliche Flüchtlingseigenschaft im Sinne von Art. 3 AsylG (SR 142.31) hindeuten. Ebensowenig lassen die Ausführungen des Beschwerdeführers im bundesgerichtlichen Verfahren erkennen, dass seine behaupteten gesundheitlichen Probleme für die Abteilung Migration zur Einschätzung führen mussten, dass der Wegweisungsvollzug geradezu undurchführbar sei (Art. 80 Abs. 6 lit. a AuG). Bei dieser Ausgangslage ist es nicht zu beanstanden, wenn die Abteilung Migration die Haftanordnung erst zurücknahm, nachdem ihr das SEM auf telefonische Nachfrage am 2. Februar 2018 in Aussicht gestellt hatte, dass gestützt auf das neue Asylgesuch wahrscheinlich ein Vollzugsstopp verfügt werde. Bis zur gleichentags verfügten Entlassung aus der Ausschaffungshaft erweist sich diese folglich nicht als widerrechtlich. Entsprechend hat das Obergericht einen Anspruch auf Haftentschädigung zu Recht verneint.
3.
Nach dem Dargelegten ist die Beschwerde abzuweisen, soweit auf sie einzutreten ist. Bei diesem Verfahrensausgang wird der Beschwerdeführer grundsätzlich kostenpflichtig (Art. 66 Abs. 1 BGG), zumal dem Gesuch um unentgeltliche Rechtspflege zufolge Aussichtslosigkeit nicht entsprochen werden kann (Art. 64 Abs. 1 BGG). Auf die Erhebung von Gerichtskosten kann jedoch aufgrund mutmasslicher Uneinbringlichkeit verzichtet werden (Art. 66 Abs. 1 BGG). Parteientschädigungen sind nicht geschuldet (Art. 68 Abs. 1 und Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit auf sie einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Es werden keine Gerichtskosten erhoben.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Obergericht des Kantons Appenzell Ausserrhoden, Einzelrichter, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 28. Juni 2018
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Fellmann