Sachverhalt: A. A.a X._ (geb. 1960) stammt aus Nigeria. Er heiratete hier nach einem erfolglosen Asylverfahren die um 18 Jahre ältere Schweizerin Y._. Gestützt hierauf erhielt er eine Aufenthaltsbewilligung. Am 6. Juli 1998 wurde er erleichtert eingebürgert. Am 14. September 1999 ist die Ehe X._ und Y._ geschieden worden, worauf X._ am 3. August 2000 die nigerianische Mutter seines am 2. November 1998 geborenen Sohnes heiratete, die in der Folge beide zu ihm in die Schweiz zogen. Am 16. Juli 2002 kam die gemeinsame Tochter A._ zur Welt. Am 9. Mai 2003 erklärte das zuständige Bundesamt die erleichterte Einbürgerung von X._ für nichtig, womit auch das Schweizer Bürgerrecht des Sohnes entfiel. A.b Am 3. Oktober 2003 wies das Ausländeramt des Kantons Schaffhausen X._ und seine beiden Kinder aus der Schweiz weg. Gleichzeitig verweigerte es seiner Ehefrau die Verlängerung der Aufenthaltsbewilligung. Mit Urteil vom 14. November 2005 bestätigte das Bundesgericht letztinstanzlich diese Anordnungen: Die Beziehung X._ und Y._ sei eine Scheinehe gewesen bzw. vor der Einbürgerung von X._ definitiv gescheitert gewesen, da er bereits damals eine aussereheliche Beziehung mit seiner künftigen Ehefrau unterhalten habe. Da keines der Familienmitglieder ein festes Anwesenheitsrecht in der Schweiz besitze und die ganze Familie gemeinsam das Land verlassen müsse, liege kein Eingriff in den Schutzbereich der Garantie auf Achtung des Familienlebens (Art. 8 EMRK) vor. B. B.a Die Familie X._ wurde in der Folge wiederholt aufgefordert, das Land zu verlassen. Sämtliche Bemühungen der Migrationsbehörden, von der nigerianischen Botschaft die notwendigen Reisepapiere für eine Ausschaffung zu erhalten, scheiterten daran, dass X._ sich konsequent weigerte, das Land zu verlassen. Er wurde deshalb erstmals am 27. September 2010 in Durchsetzungshaft genommen, welche auf Beschwerde hin vom Bundesgericht aus formellen Gründen mit Urteil vom 24. Dezember 2010 aufgehoben wurde. Am 16. Januar 2011 wurde X._ erneut in Durchsetzungshaft genommen und im Rahmen von Haftprüfungen wurde die Rechtsmässigkeit der Aufrechterhaltung der Durchsetzungskraft bis - schliesslich - 16. Juni 2011 bestätigt, zuletzt mit Entscheid des Kantonsgerichts Schaffhausen vom 12. April 2011. B.b X._ beschwerte sich dagegen am 2. Mai 2011 beim Obergericht des Kantons Schaffhausen, welches die Beschwerde mit Entscheid vom 20. Mai 2011 abwies. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 26. Mai 2011 beantragt X._, den Entscheid des Obergerichts vom 20. Mai 2011 aufzuheben, die Rechtmässigkeit der Verlängerung der Durchsetzungshaft nicht zu bestätigen und ihn aus der Durchsetzungshaft zu entlassen. Das Migrationsamt, das Kantonsgericht und das Obergericht des Kantons Schaffhausen verzichten auf eine Vernehmlassung. Das Bundesamt für Migration hat innert Frist nicht Stellung genommen.