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.