Sachverhalt:
A. A.a Der nach eigenen Angaben aus der Elfenbeinküste stammende X._ wurde am 20. Dezember 2000 nach einem illegalen Grenzübertritt in der Schweiz polizeilich angehalten. Am 19. Juni 2001 wies das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) ein Asylgesuch von X._ ab und wies ihn aus der Schweiz weg. Vom 14. März bis zum 15. Juni 2001 befand er sich in Vorbereitungshaft, vom 15. Juni 2001 bis zum 23. Januar 2002 erstmals in Ausschaffungshaft. Mit Urteil 2A.14/2002 vom 23. Januar 2002 hiess das Bundesgericht eine Beschwerde gegen eine weitere Haftverlängerung gut und ordnete die unverzügliche Haftentlassung an, weil die Behörden während längerer Zeit keine zielgerichteten Schritte im Hinblick auf den Ausschaffungsvollzug mehr unternommen und insoweit gegen das ihnen obliegende Beschleunigungsgebot verstossen hatten.
A.b Am 11. Mai 2006 wies das Bundesamt für Migration ein Wiedererwägungsgesuch hinsichtlich der Wegweisung ab. Am 12. April 2006 sowie am 22. Februar 2007 wurde X._ erfolglos der ivorischen Botschaft vorgeführt. Am 23. Januar 2009 ordnete das Amt für Migration Basel-Landschaft erneut die Ausschaffungshaft an. Gleichentags prüfte und bestätigte der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Kantonsgericht Basel-Landschaft die Haft. Am 5. März 2009 fand eine Befragung durch eine ivorische Delegation statt, die ebenfalls ergebnislos verlief.
A.c Mit Schreiben vom 14. April 2009 beantragte das Amt für Migration Basel-Landschaft die Verlängerung der Ausschaffungshaft. Am 15. April 2009 gab der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Kantonsgericht Basel-Landschaft (als Haftrichter) diesem Antrag statt und verlängerte die Haft bis zum 21. Juli 2009.
B. B.a Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 27. April 2009 an das Bundesgericht beantragt X._, das Urteil des Haftrichters aufzuheben und die sofortige Haftentlassung anzuordnen. Überdies ersucht er um unentgeltliche Rechtspflege unter Einschluss der unentgeltlichen Verbeiständung.
B.b Das Amt für Migration Basel-Landschaft schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Kantonsgericht Basel-Landschaft hat auf eine Stellungnahme verzichtet. Das Bundesamt für Migration erachtet das Hafturteil in seiner Vernehmlassung als rechtmässig, ohne einen ausdrücklichen Antrag zu stellen.
B.c Mit Eingabe vom 26. Mai 2009 hat sich X._ nochmals zur Sache geäussert.

Erwägungen:
1. Gegen den angefochtenen kantonal letztinstanzlichen Haftentscheid steht praxisgemäss die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen.
2. Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, so kann die zuständige Behörde nach Art. 76 Abs. 1 AuG die betroffene ausländische Person zur Sicherstellung des Vollzugs bei Vorliegen bestimmter Haftgründe in Haft nehmen. Zu diesen Haftgründen zählt unter anderem, dass konkrete Anzeichen befürchten lassen, die ausländische Person wolle sich der Ausschaffung entziehen, insbesondere weil sie ihrer Mitwirkungspflicht nicht nachkommt (sog. Untertauchensgefahr; Art. 76 Abs. 1 lit. b Ziff. 3 AuG); bei einem straffälligen Ausländer ist eher als bei einem unbescholtenen davon auszugehen, er werde in Zukunft behördliche Anordnungen missachten (vgl. <ref-ruling> E. 3 S. 58 f.; <ref-ruling> E. 2a, 148 E. 2b/aa S. 152; <ref-ruling> E. 2b S. 198). Ein weiterer Haftgrund liegt darin, dass der Ausländer andere Personen ernsthaft bedroht oder an Leib und Leben erheblich gefährdet und deshalb strafrechtlich verfolgt wird oder verurteilt worden ist (Art. 76 Abs. 1 lit. b Ziff. 1 in Verbindung mit Art. 75 Abs. 1 lit. g AuG). Weiter muss sich die Haft als verhältnismässig erweisen, und der Vollzug der Weg- oder Ausweisung darf nicht aus rechtlichen oder tatsächlichen Gründen undurchführbar sein (vgl. Art. 80 Abs. 6 lit. a AuG). Auf Seiten der Behörden ist die Papierbeschaffung sodann mit dem nötigen Nachdruck zu verfolgen (Art. 76 Abs. 4 AuG). Die Haft darf höchstens drei Monate dauern; stehen dem Vollzug der Weg- oder Ausweisung besondere Hindernisse entgegen, so kann sie mit Zustimmung des Haftrichters um höchstens 15 Monate verlängert werden (Art. 76 Abs. 3 AuG).
3. 3.1 Der Beschwerdeführer wurde am 23. Februar 2001 wegen Widerhandlung gegen das Betäubungsmittelgesetz zu einer 18-monatigen bedingten Freiheitsstrafe verurteilt. Damit erweist sich der Haftgrund von Art. 76 Abs. 1 lit. b Ziff. 1 in Verbindung mit Art. 75 Abs. 1 lit. g AuG als erfüllt.
3.2 Der Beschwerdeführer bestreitet die Untertauchensgefahr bzw. die ihm zur Last gelegte fehlende Mitwirkung am Wegweisungsvollzug. Vielmehr sei er bereit, in die Elfenbeinküste auszureisen, könne aber die nötigen Papiere nicht beschaffen, da er als ivorischer Staatsbürger nicht anerkannt werde. Indessen vermag der Beschwerdeführer überhaupt nicht zu belegen, dass er sich je um eine Ausreise bemüht hätte. Inzwischen befindet er sich immerhin seit mehr als acht Jahren in der Schweiz und hätte daher genügend Zeit gehabt, die nötigen Vorbereitungen für eine Ausreise zu treffen. Zugleich bestehen Hinweise dafür, dass er nicht aus der Elfenbeinküste stammt. Einerseits soll er das sogar gegenüber Vertretern der Elfenbeinküste ausgesagt haben, ohne seine wahre Herkunft preiszugeben, andererseits sprach er bei der Befragung durch eine ivorische Delegation am 5. März 2009, an der auch ein Vertreter des Bundesamts für Migration teilnahm, konsequent nur Englisch und nicht Französisch. Seine Begründung, er habe lediglich in der Sprache geantwortet, in der ihm Fragen gestellt worden seien, überzeugt insoweit nicht. Eine Richtigstellung wäre ihm durchaus zumutbar gewesen, dies um so mehr, als bereits zwei frühere Vorführungen in den Jahren 2006 und 2007 vor der ivorischen Botschaft erfolglos verlaufen waren. Die Annahme, der Beschwerdeführer habe nicht das ihm Mögliche unternommen, um seine Herkunft klarzustellen und die Voraussetzungen einer Ausreise zu erfüllen, ist damit nicht offensichtlich unrichtig und nicht zu beanstanden (vgl. Art. 97 und 105 BGG). Zwar trifft es zu, dass es von den Befragungen keine aktenkundigen Protokolle gibt, wie der Beschwerdeführer geltend macht, doch können formelle Anforderungen an das Verfahren bei Befragungen durch ausländische Behörden über die Rücknahme bzw. über die Abklärung der Herkunft möglicher Landsleute nicht in gleicher Weise gestellt werden wie bei rein inländischen Ermittlungshandlungen. Unter diesen Umständen ist nicht zuletzt auch mit Blick auf die Straffälligkeit des Beschwerdeführers der Haftgrund von Art. 76 Abs. 1 lit. b Ziff. 3 AuG ebenfalls erfüllt.
3.3 Zutreffend geht der Haftrichter sodann davon aus, dass zu den besonderen Hindernissen, die nach Art. 76 Abs. 3 AuG eine Haftverlängerung zu rechtfertigen vermögen, aussergewöhnliche Schwierigkeiten bei der Papierbeschaffung oder Probleme bei der Organisation der zwangsweisen Rückschaffung zählen. Unter Verhältnismässigkeitsgesichtspunkten ist weiter zu berücksichtigen, dass der Beschwerdeführer die Verzögerung der Ausreise mit zu verantworten hat. Die Behörden durften ihn nach rund sieben Jahren mit Blick auf einen neuen ernsthaften Ausschaffungsversuch verbunden mit der Verletzung der Mitwirkungspflicht durch den Beschwerdeführer auch wieder in Haft nehmen (dazu Thomas Hugi Yar, § 10 Zwangsmassnahmen im Ausländerrecht, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl., 2009, Rz. 10.158 ff.). Im weiteren Verlauf wird allerdings die zulässige Höchstdauer der Haft im Auge behalten werden müssen (dazu Art. 79 AuG).
3.4 Allein der Umstand, dass sich eine Ausreise nur schwer organisieren lässt, macht die Ausschaffung nicht undurchführbar im Sinne von Art. 80 Abs. 5 AuG. Die Haft ist nur dann unzulässig, wenn keine oder bloss eine höchst unwahrscheinliche, rein theoretische Möglichkeit besteht, die Wegweisung zu vollziehen, nicht indessen bei einer ernsthaften, wenn auch allenfalls noch geringen Aussicht hierauf (<ref-ruling> E. 4 S. 59 ff.). Aufgrund der bisherigen Erfahrungen erscheint eine Herkunft aus einem anglophonen Staat Westafrikas möglich. Der Beschwerdeführer wurde offenbar bereits von den malischen Behörden nicht anerkannt. Im Vordergrund stehen nunmehr Sierra Leone, Gambia und Liberia. Da diese drei Staaten über keine Botschaft in der Schweiz verfügen, müssen entsprechende Delegationen eingeladen werden, um Identitätsbefragungen durchzuführen. Solche sind gemäss Angaben des Bundesamts für Migration jedenfalls für Gambia und Liberia für den Sommer 2009 in Planung. Die entsprechenden Abklärungen zwecks Vorbereitung der Ausschaffung erweisen sich zwar insgesamt als aufwendig; der Wegweisungsvollzug ist aber nicht lediglich rein theoretischer Natur.
3.5 Bis zum hier massgeblichen Zeitpunkt der haftrichterlichen Verhandlung über die Haftverlängerung haben die Behörden schliesslich auch nicht gegen das Beschleunigungsgebot verstossen. Nebst der Befragung durch die ivorische Delegation am 5. März 2009 ist aktenkundig, dass bis jedenfalls zum Datum der Haftrichterverhandlung am 15. April 2009 eine rege Zusammenarbeit zwischen kantonalen Behörden und dem Bundesamt für Migration bestand im Hinblick auf die Ermöglichung der Ausschaffung des Beschwerdeführers. Die Behörden werden allerdings das Beschleunigungsgebot auch weiterhin zu beachten haben.
3.6 Die Verlängerung der Ausschaffungshaft erweist sich demnach als rechtmässig. Nur der Ergänzung halber sei darauf hingewiesen, dass gegenüber dem Beschwerdeführer aufgrund seiner mangelhaften Mitwirkung die Anordnung von Durchsetzungshaft gemäss Art. 78 AuG geprüft werden könnte, falls die Ausschaffungshaft unzulässig wäre oder dies allenfalls mit der Zeit würde.
4. 4.1 Die Beschwerde erweist sich als unbegründet und ist abzuweisen.
4.2 Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Nach Art. 64 AuG wird dies bei Bedürftigkeit gewährt, sofern die Rechtsbegehren nicht aussichtslos erscheinen. Gemäss der bundesgerichtlichen Rechtsprechung darf einem bedürftigen Häftling im Haftverlängerungsverfahren nach drei Monaten der unentgeltliche Rechtsbeistand grundsätzlich nicht verweigert werden (<ref-ruling> E. 3.2 S. 99 ff.; <ref-ruling> E. 3b S. 276 ff.; Hugi Yar, a.a.O., Rz. 10.41). Diese Rechtsprechung gilt allerdings für die haftrichterliche Überprüfung des Haftentscheids und setzt an sich ein entsprechendes Gesuch des Häftlings vor dem Haftrichter voraus. Sie gilt nicht ohne weiteres auch für eine richterliche Rechtsmittelinstanz, namentlich für das Bundesgericht. Im vorliegenden Fall hat der Beschwerdeführer vor dem Haftrichter kein Gesuch um unentgeltliche Verbeiständung gestellt, und er war damals auch nicht anwaltlich vertreten. Selbst wenn nicht von einem vorbehaltlosen Anspruch auf unentgeltliche Rechtspflege auszugehen ist, rechtfertigt dies doch eher die Gewährung der unentgeltlichen Rechtsprechung und Verbeiständung, als wenn bereits vor dem Haftrichter ein unentgeltlich eingesetzter Anwalt tätig war. In diesem Sinne sind für das bundesgerichtliche Verfahren keine Kosten zu erheben, und der Rechtsvertreter des bedürftigen Beschwerdeführers ist angemessen aus der Bundesgerichtskasse zu entschädigen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Es werden keine Kosten erhoben.
4. Advokat Dr. Stefan Suter wird als amtlicher Vertreter des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse ein Honorar von Fr. 1'500.-- ausgerichtet.
5. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Migration und dem Kantonsgericht Basel-Landschaft, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 3. Juni 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Uebersax