Sachverhalt: Sachverhalt: A. X._ wurde am 15. Oktober 2004 von der Kantonspolizei Appenzell A.Rh. festgenommen und dem Verhörrichter des Kantons Appenzell A.Rh. zugeführt; dieser eröffnete gegen ihn ein Strafverfahren und nahm ihn am gleichen Tag in Untersuchungshaft. Vorgeworfen wurden ihm - wenn auch nicht ausdrücklich - Drohung (Art. 180 Abs. 1 StGB) und Vorbereitungshandlungen zu vorsätzlicher Tötung bzw. Mord (Art. 260bis Abs. 1 StGB). Die Anzeige war vom Sozialpsychiatrischen Dienst des Psychiatrischen Zentrums in Herisau erstattet worden. Danach soll der Beschuldigte in zwei Therapiegesprächen konkrete Gewaltdrohungen gegen eine Drittperson geäussert haben, die er für den Tod seines Vaters im Jahre 1989 verantwortlich machte; gefährdet sei nach der Anzeige allenfalls auch die Therapeutin selbst, die den angeblichen Gesprächsinhalt weitergab. Der Verhörrichter erachtete die Bedrohungslage insbesondere vor dem Hintergrund der geplanten Ausschaffung des Verhafteten nach der rechtskräftigen Abweisung seines Asylgesuchs als ernsthaft. Der Beschuldigte bestritt die ihm zur Last gelegten Äusserungen wie auch das Bestehen von Racheplänen. Im Haftprüfungsverfahren bestätigte der Präsident des Kantonsgerichts von Appenzell A.Rh. die Untersuchungshaft mit Entscheid vom 19. Oktober 2004. Er nahm einen dringenden Tatverdacht im Hinblick auf Art. 260bis StGB an. Ausserdem bejahte er den im kantonalen Verfahrensrecht vorgesehenen besonderen Haftgrund der Ausführungsgefahr. Er verfügte, die Haft falle dahin, wenn nicht innert 20 Tagen um Verlängerung nachgesucht werde. Im Haftprüfungsverfahren bestätigte der Präsident des Kantonsgerichts von Appenzell A.Rh. die Untersuchungshaft mit Entscheid vom 19. Oktober 2004. Er nahm einen dringenden Tatverdacht im Hinblick auf Art. 260bis StGB an. Ausserdem bejahte er den im kantonalen Verfahrensrecht vorgesehenen besonderen Haftgrund der Ausführungsgefahr. Er verfügte, die Haft falle dahin, wenn nicht innert 20 Tagen um Verlängerung nachgesucht werde. B. Gegen den Haftprüfungsentscheid erhob X._ am 26. Oktober 2004 staatsrechtliche Beschwerde (Verfahren 1P.618/2004). In der Folge wurde der Vollzug der Ausschaffung aufgeschoben. Ausserdem sah die Drittperson, auf die sich die Drohungen bezogen haben sollen, einstweilen davon ab, einen Strafantrag zu stellen. Der Verhörrichter ging daher vom Wegfall der Voraussetzungen der Untersuchungshaft aus und liess den Beschuldigten am 5. November 2004 frei. X._ zog am 12. November 2004 die staatsrechtliche Beschwerde zurück; das bundesgerichtliche Verfahren wurde am 16. November 2004 als erledigt abgeschrieben. B. Gegen den Haftprüfungsentscheid erhob X._ am 26. Oktober 2004 staatsrechtliche Beschwerde (Verfahren 1P.618/2004). In der Folge wurde der Vollzug der Ausschaffung aufgeschoben. Ausserdem sah die Drittperson, auf die sich die Drohungen bezogen haben sollen, einstweilen davon ab, einen Strafantrag zu stellen. Der Verhörrichter ging daher vom Wegfall der Voraussetzungen der Untersuchungshaft aus und liess den Beschuldigten am 5. November 2004 frei. X._ zog am 12. November 2004 die staatsrechtliche Beschwerde zurück; das bundesgerichtliche Verfahren wurde am 16. November 2004 als erledigt abgeschrieben. C. Am 20. Dezember 2004 stellte der Verhörrichter das Strafverfahren ein, auferlegte dem Beschuldigten aber die Untersuchungskosten. Bereits am 22. November 2004 hatte dieser um eine Entschädigung von insgesamt Fr. 10'000.-- "für seine Anwaltskosten und als Genugtuungssumme für nicht nur ungerechtfertigte, sondern illegale Haft von 20 Tagen" ersucht. Der Verhörrichter nahm im Dispositiv der Verfügung keinen Bezug auf diesen Antrag. Er führte jedoch in den Erwägungen aus, die gesetzlichen Voraussetzungen für eine Entschädigung bzw. Genugtuung seien nicht erfüllt. Die Staatsanwaltschaft des Kantons Appenzell-Ausserrhoden wies den Rekurs von X._ gegen diese Verfügung am 10. Februar 2005 vollumfänglich ab. In der Rekursschrift war unter anderem beantragt worden, vom Verhöramt sei eine angemessene Parteientschädigung sowie eine Genugtuung im Sinne seiner Begehren zuzusprechen. Die Staatsanwaltschaft behandelte diesen Rekursantrag in den Erwägungen; sie erachtete die Verweigerung einer Parteientschädigung und einer Genugtuung für die Untersuchungshaft als rechtmässig. Die Staatsanwaltschaft des Kantons Appenzell-Ausserrhoden wies den Rekurs von X._ gegen diese Verfügung am 10. Februar 2005 vollumfänglich ab. In der Rekursschrift war unter anderem beantragt worden, vom Verhöramt sei eine angemessene Parteientschädigung sowie eine Genugtuung im Sinne seiner Begehren zuzusprechen. Die Staatsanwaltschaft behandelte diesen Rekursantrag in den Erwägungen; sie erachtete die Verweigerung einer Parteientschädigung und einer Genugtuung für die Untersuchungshaft als rechtmässig. D. X._ führt staatsrechtliche Beschwerde mit dem Antrag, den Rekursentscheid der Staatsanwaltschaft aufzuheben. Er rügt eine Verletzung seines Anspruchs auf einen verfassungsmässigen Richter (Art. 30 BV) sowie eine willkürliche Tatsachenfeststellung und Anwendung des kantonalen Rechts (Art. 9 BV); gleichzeitig sei gegen Art. 29 und Art. 31 Abs. 1 BV bzw. Art. 5 Ziff. 5 EMRK verstossen worden. Ausserdem stellt er ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren. Die Staatsanwaltschaft ersucht um Abweisung der Beschwerde. In der Replik hat der Beschwerdeführer an seinen Anträgen festgehalten. Die Staatsanwaltschaft ersucht um Abweisung der Beschwerde. In der Replik hat der Beschwerdeführer an seinen Anträgen festgehalten. E. Mit Formularverfügung vom 23. Mai 2005 hat der Präsident der I. öffentlichrechtlichen Abteilung bis zum Entscheid über das im Nachgang zur Replik gestellte Gesuch um aufschiebende Wirkung superprovisorisch alle Vollziehungsvorkehrungen untersagt.