Sachverhalt: A. X._ (geb. 1989) stammt aus Sri Lanka. Das Bundesamt für Migration wies am 18. Januar 2012 sein Asylgesuch ab; eine Beschwerde an das Bundesverwaltungsgericht hiergegen blieb am 7. November 2012 ohne Erfolg. X._ verliess trotz entsprechender Aufforderungen die Schweiz nicht, worauf am 10. Dezember 2012 das Verfahren eingeleitet wurde, um für ihn ein Ersatzreisepapier zu beschaffen. B. Am 26. Dezember 2012 teilte sein neuer Anwalt dem Migrationsamt Appenzell Ausserrhoden mit, dass er für seinen Mandanten ein neues Asylgesuch einreichen werde, weshalb mit Vollzugsmassnahmen noch zuzuwarten sei. X._ sprach am 4. Januar 2013 auf dem Migrationsamt Appenzell Ausserrhoden vor, wo er um 15.30 Uhr in Ausschaffungshaft genommen wurde. Die entsprechende Verfügung ist am 7. Januar 2013 begründet worden. Am 7. bzw. 14. Januar 2013 setzte die Instruktionsrichterin im Rahmen des Revisionsverfahrens gegen das bundesverwaltungsgerichtliche Urteil vom 7. November 2012 den Vollzug der Wegweisung von X._ aus. Der Einzelrichter am Obergericht Appenzell Ausserrhoden prüfte die Haft am 8. Januar 2013 und genehmigte sie bis zum 3. Juli 2013. C. X._ beantragt vor Bundesgericht, den Entscheid des Obergerichts Appenzell Ausserrhoden, Einzelrichter, aufzuheben; er sei aus der Ausschaffungshaft zu entlassen. Für das bundesgerichtliche Verfahren sei ihm die unentgeltliche Rechtspflege und Verbeiständung und für die ausgestandene Haft eine Entschädigung zu gewähren. Das Amt für Migration und das Obergericht Appenzell Ausserrhoden beantragen, die Beschwerde abzuweisen. Das Bundesamt für Migration weist daraufhin, dass ein zwangsweiser Wegweisungsvollzug nach Sri Lanka grundsätzlich möglich sei und durchgeführt werde. X._ hat an seinen Anträgen und Ausführungen festgehalten. 