Das Bundesgericht stellt fest und zieht in Erwägung:
1. Der aus Algerien stammende X._ (geb. 1979) - alias A._, alias B._, alias C._, alias D._ - reiste im Jahre 1997 illegal in die Schweiz ein und stellte unter dem letztgenannten Familiennamen ein Asylgesuch. Das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) wies dieses Gesuch mit Verfügung vom 7. August 1997 ab und den Gesuchsteller aus der Schweiz weg. Eine hiegegen erhobene Beschwerde wies die Schweizerische Asylrekurskommission mit Urteil vom 15. Januar 1998 ab. X._ hätte daraufhin die Schweiz bis zum 28. Februar 1998 verlassen sollen. Mit Entscheid des Kreispräsidenten Chur (als Haftrichter) vom 6. November 2000 wurde die in der Folge (am 2. November 2000) gegen X._ angeordnete Ausschaffungshaft bis zum 1. Februar 2001 bestätigt, nachdem u. a. Interpol Algier mitgeteilt hatte, der Genannte sei in Algerien unter diesem Namen bereits daktyloskopisch erfasst. Aus der bis zum 30. Mai 2001 verlängerten Ausschaffungshaft wurde X._ mit Verfügung des Amtes für Polizeiwesen vom 28. Mai 2001 schliesslich entlassen, nachdem für ihn die erforderlichen Reisepapiere nicht beschafft werden konnten.
In den folgenden Jahren befand sich X._ verschiedentlich im Strafvollzug (zuletzt vom 6. Juni 2005 bis zum 28. November 2007 u.a. wegen Betäubungsmitteldelikten und einfacher Körperverletzung). Am 31. März 2007 hatte er durch renitentes Verhalten am Flughafen Zürich seine Ausschaffung verhindert, nachdem er - unter Vorbehalt des Vollzugs dieser Massnahme - vorzeitig bedingt aus dem Strafvollzug entlassen worden war. Er wurde daher in den ordentlichen Strafvollzug zurückversetzt und auf dessen Ende (28. November 2007) vom Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden in Durchsetzungshaft genommen. Das Bezirksgerichtspräsidium Plessur prüfte und bewilligte diese Massnahme zunächst bis zum 27. Dezember 2007. Mit Entscheid vom 21. Dezember 2007 bewilligte es die Verlängerung der Durchsetzungshaft bis zum 27. Februar 2008, und mit Entscheid vom 23. April 2008 deren weitere Verlängerung bis zum 27. Juni 2008.
2. Mit Eingabe vom 29. April 2008 führt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, den letztgenannten Entscheid des Bezirksgerichtspräsidiums Plessur aufzuheben und ihn - den Beschwerdeführer - sofort aus der Durchsetzungshaft zu entlassen. Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht.
Die kantonalen Akten sind eingeholt, ein Schriftenwechsel ist nicht durchgeführt worden. Das Urteil ergeht im vereinfachten Verfahren nach <ref-law> (summarische Begründung).
3. 3.1 Hat ein Ausländer seine Pflicht zur Ausreise aus der Schweiz innert der ihm angesetzten Frist nicht erfüllt und kann die rechtskräftige Weg- oder Ausweisung wegen seines persönlichen Verhaltens nicht vollzogen werden, so darf er, um der Ausreisepflicht Nachachtung zu verschaffen, in Durchsetzungshaft genommen werden, sofern die Anordnung der Ausschaffungshaft nicht zulässig ist und keine andere, mildere Massnahme besteht (Art. 78 Abs. 1 AuG [SR 142.20]). Die Durchsetzungshaft ist erstmals für einen Monat zulässig. Sie kann hernach mit der Zustimmung der zuständigen kantonalen richterlichen Behörde - bis zu einer Maximaldauer von 18 Monaten - jeweils in Schritten von je zwei Monaten verlängert werden (Art. 78 Abs. 2 AuG). Die Vorbereitungs-, Ausschaffungs- und Durchsetzungshaft dürfen zusammen die Höchstdauer von 24 Monaten nicht überschreiten (Art. 79 AuG).
3.2 Zweck der Durchsetzungshaft ist es, die ausreisepflichtige Person in jenen Fällen zu einer Verhaltensänderung zu bewegen, in denen nach Ablauf der Ausreisefrist der Vollzug der rechtskräftig gegen sie angeordneten Weg- oder Ausweisung - trotz der behördlichen Bemühungen - ohne ihre Kooperation nicht möglich ist. Sie soll das letzte Mittel darstellen, wenn und soweit keine andere Zwangsmassnahme mehr zum Ziel führt, den illegal anwesenden Ausländer - auch gegen seinen Willen - in seine Heimat verbringen zu können (<ref-ruling> E. 2.2 S. 99 f.). Ihre konventionsrechtliche Rechtfertigung findet die Durchsetzungshaft in Art. 5 Ziff. 1 lit. f in Verbindung mit Art. 5 Ziff. 1 lit. b EMRK. Nach dem Willen des Gesetzgebers kann - je nach den Umständen - selbst eine Haftdauer von 18 Monaten im Einzelfall verhältnismässig sein (vgl. <ref-ruling> E. 2.2 S. 100; zur Publikation bestimmtes Urteil 2C_556/2007 vom 21. Januar 2008, E. 2).
3.2 Zweck der Durchsetzungshaft ist es, die ausreisepflichtige Person in jenen Fällen zu einer Verhaltensänderung zu bewegen, in denen nach Ablauf der Ausreisefrist der Vollzug der rechtskräftig gegen sie angeordneten Weg- oder Ausweisung - trotz der behördlichen Bemühungen - ohne ihre Kooperation nicht möglich ist. Sie soll das letzte Mittel darstellen, wenn und soweit keine andere Zwangsmassnahme mehr zum Ziel führt, den illegal anwesenden Ausländer - auch gegen seinen Willen - in seine Heimat verbringen zu können (<ref-ruling> E. 2.2 S. 99 f.). Ihre konventionsrechtliche Rechtfertigung findet die Durchsetzungshaft in Art. 5 Ziff. 1 lit. f in Verbindung mit Art. 5 Ziff. 1 lit. b EMRK. Nach dem Willen des Gesetzgebers kann - je nach den Umständen - selbst eine Haftdauer von 18 Monaten im Einzelfall verhältnismässig sein (vgl. <ref-ruling> E. 2.2 S. 100; zur Publikation bestimmtes Urteil 2C_556/2007 vom 21. Januar 2008, E. 2).
3.3 Die umstrittene ausländerrechtliche Festhaltung entspricht diesen Vorgaben und verletzt kein Bundesrecht:
3.3.1 Der Beschwerdeführer ist im Asylverfahren rechtskräftig aus der Schweiz weggewiesen worden und hätte diese bis zum 28. Februar 1998 verlassen müssen. Er hat sich während Jahren geweigert, bei der Feststellung seiner Identität und der Beschaffung von Reisepapieren mitzuwirken und musste - wegen rechtlicher bzw. tatsächlicher Unmöglichkeit der Ausschaffung - im Jahre 2001 bereits einmal aus der Ausschaffungshaft entlassen werden. Nachdem für ihn - während er sich im ordentlichen Strafvollzug (u.a. wegen Betäubungsmitteldelikten) befand - via die algerische Vertretung in der Schweiz ein Reisepapier hatte erhältlich gemacht werden können, verweigerte er durch renitentes Verhalten am Flughafen seine Ausschaffung und trat den für ihn gebuchten Rückflug am 31. Mai 2007 nicht an. Es ist mit der Vorinstanz davon auszugehen, dass der Beschwerdeführer - der sich in der Haftrichterverhandlung vom 23. April 2008 klarerweise dahingehend geäussert hat - sich weiterhin weigert, freiwillig nach Algerien auszureisen, und nicht bereit ist, mit den Behörden hierfür zu kooperieren (weshalb die zwangsweise Ausschaffung zur Zeit rechtlich und tatsächlich als unmöglich erscheint; zu Algerien vgl. <ref-ruling> E. 3.3 sowie das zur Veröffentlichung bestimmte Urteil 2C_556/2007 vom 21. Januar 2008, E. 2).
3.3.2 Was der Beschwerdeführer einwendet, überzeugt nicht: Er verfügt in der Schweiz über kein Anwesenheitsrecht, auch wenn sein Aufenthalt wegen seines renitenten Verhaltens bisher geduldet werden musste. Die umstrittene Verlängerung seiner Festhaltung ist nicht unverhältnismässig. Würde er mit den Behörden zusammenarbeiten, könnte seine Wegweisung innert weniger Wochen vollzogen werden. In diesem Zusammenhang ist nicht ersichtlich, was die zuständigen Behörden hinsichtlich der Beschleunigung des Verfahrens noch vorkehren sollten, nachdem die algerische Vertretung für den Beschwerdeführer bereits einmal ein Reisepapier ausgestellt hat und die mögliche Wiederbeschaffung eines solchen allein vom Verhalten des Beschwerdeführers abhängt. Es kann nicht ausgeschlossen werden, dass dieser sich doch noch eines Besseren besinnen und im Verlaufe der verlängerten Durchsetzungshaft nunmehr mit den Behörden kooperieren wird. Seine Beteuerungen, er werde im Falle seiner Freilassung die Schweiz innert 48 Stunden verlassen ("auch 24 Stunden sind genug"), sind unbeachtlich: Es ist nicht ersichtlich, wie er sich ohne Reisepapier zulässigerweise in einen Drittstaat begeben könnte. Die schweizerischen Behörden dürfen nicht bewusst zu einer illegalen Einreise in einen solchen Hand bieten (<ref-ruling> E. 4.2.2).
Für alles Weitere wird auf die zutreffenden Ausführungen im angefochtenen Entscheid verwiesen (<ref-law>).
4. Nach dem Gesagten ist die offensichtlich unbegründete Beschwerde abzuweisen.
Dem Verfahrensausgang entsprechend würde der unterliegende Beschwerdeführer kostenpflichtig (<ref-law>). Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann mangels ernsthafter Erfolgsaussichten der Beschwerde nicht entsprochen werden (vgl. <ref-law>). Es rechtfertigt sich jedoch aufgrund der Umstände, von der Erhebung von Kosten abzusehen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Es werden keine Kosten erhoben.
4. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Polizeiwesen und Zivilrecht Graubünden, dem Bezirksgerichtspräsidium Plessur und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 20. Mai 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Klopfenstein