Sachverhalt:
A. Die Schweizer Bürger B._ und A._ haben am 18. August 1994 in Muttenz geheiratet. Am 10. Januar 2002 kam ihre gemeinsame Tochter C._ zur Welt. Im Januar 2004 wanderte die Familie nach Südafrika aus. Bei einem erneuten Aufenthalt in der Schweiz kam am 23. März 2004 der gemeinsame Sohn D._ auf die Welt, wobei die Familie kurz nach der Geburt wieder nach Südafrika zurückflog.
Die ersten 18 Monate lebten die Eltern gemeinsam mit den Kindern in Somerset West (gediegener Vorort von Kapstadt). Danach nahm der Vater eine Stelle in Johannesburg an und pendelte während vier Jahren zwischen Somerset West und Johannesburg (Montag Abreise, Donnerstag Rückreise). Nachdem er diese Stelle im Juli 2009 verloren hatte, nahm er eine Stelle bei einer Schweizer Firma in Deutschland an. In dieser Zeit verbrachte er die Ferien und kumulierte Überstunden in Südafrika bei der Familie und telefonierte mehrmals wöchentlich mit ihr. Im April 2011 zog der Vater zurück nach Südafrika und liess sich aufgrund des Arbeitsmarktes und der ab dem Jahr 2010 aufgetretenen ehelichen Spannungen wieder in Johannesburg nieder, wo er seither mit seiner neuen Partnerin und deren Sohn lebt. Nach seinen Angaben besuchte er die Kinder seither alle zwei Wochen von Freitagabend bis Montagmorgen in Somerset West, telefonierte jeden zweiten Tag mit ihnen und verbrachte auch die Ferien mit ihnen; nach Darstellung der Mutter erfolgten die Besuche ungefähr einmal pro Monat. Beide Kinder gingen in Somerset West zur Schule; die Tochter besuchte zuletzt die dritte, ihr jüngerer Bruder die erste Klasse.
Am 6. August 2011 erhielt der Vater von der Mutter eine SMS mit dem Inhalt, es sei wegen einer Geburtstagsparty nicht möglich, dass er die Kinder wie geplant zu sich auf Besuch nehmen könne. Am 10. August 2011 gingen die Kinder zum letzten Mal zur Schule. Am 12. August 2011 verbrachte sie die Mutter ohne Wissen des Vaters in die Schweiz. Die Kinder selbst wurden von der Mutter erst am Flughafen bzw. im Flugzeug über Ziel und Zweck der Reise informiert.
B. Mit Gesuch vom 22. September 2011 beantragte der Vater die Rückführung der Kinder nach Südafrika und die Kontaktregelung für die Dauer des Verfahrens.
Am 27. September 2011 verfügte der Appellationsgerichtspräsident Basel-Stadt ein Ausreiseverbot (mit Ausnahme von Südafrika) und die Hinterlegung sämtlicher Reisepapiere der Kinder sowie ein Verbot, neue Papiere zu beantragen. Dem Vater wurde das Recht eingeräumt, alle zwei Tage mit den Kindern zu telefonieren oder per Skype oder E-Mail zu kommunizieren. Sodann wurde ihnen eine Rechtsvertreterin bestellt.
Am 13. Oktober 2011 reichte die Kindesvertreterin eine Zusammenfassung des Gesprächs mit den Kindern ein und am 19. Oktober 2011 wurden sie durch den Appellationsgerichtspräsidenten und Dr. phil. E._ angehört. Am 3. November 2011 fand das Vermittlungsverfahren statt, bei welchem beide Parteien anwesend waren. Es wurde ein Vergleich geschlossen, den die Mutter am 7. November 2011 widerrief. Vorgängig war auch eine Mediation ins Auge gefasst, angesichts der unvereinbaren Parteistandpunkte aber nicht durchgeführt worden.
Mit an der Hauptverhandlung vom 7. November 2011, von welcher der nach Südafrika zurückgereiste Vater dispensiert worden war und an welchem die Mutter nochmals angehört wurde, gefälltem Urteil hiess der Appellationsgerichtspräsident den Rückführungsantrag des Vaters und der Kindesvertreterin gut, indem er die Mutter verpflichtete, die Kinder bis spätestens 28. Dezember 2011 auf ihre Kosten nach Südafrika zurückzuführen oder zurückführen zu lassen oder dem Vater zwecks Rückführung nach Südafrika zu übergeben, unter Anweisung der jeweils kantonal zuständige Vollzugsbehörde, im Weigerungsfall innert 60 Tagen seit Urteilszustellung die Kinder nach Südafrika zurückzuführen oder sie vom Gesuchsteller in der Schweiz abholen zu lassen. Sodann wurden die Vollzugsmodalitäten (Übergabe der Reisedokumente etc.) sowie das Kommunikationsrecht zwischen Vater und Kindern bis zum Rückführungszeitpunkt geregelt.
C. Gegen dieses Urteil hat A._ am 5. Dezember 2011 eine Beschwerde in Zivilsachen erhoben mit den Begehren um dessen Aufhebung und Abweisung des Rückführungsgesuches, eventualiter um Rückweisung der Sache an die Vorinstanz zur Ermittlung des Sachverhaltes und zur Neubeurteilung, subeventualiter um Erlass folgender Auflagen im Zusammenhang mit der Rückführung: Verpflichtung des Vaters zur Anmeldung der Kinder an einer Schule in der Region Somerset West, zur Bezahlung der Schulkosten für zwei Jahre sowie zur Bezahlung des Mietzinsdepots und einer Wohnung in der Region Somerset West im Umfang von ca. Rand 8'500.-- pro Monat und Sicherstellung der entsprechenden Beträge.
Mit Vernehmlassungen vom 15. Dezember 2011 verlangen sowohl der Vater als auch die Kindesvertreterin die Abweisung der Beschwerde und die Rückführung der Kinder. Der Vater beantragt zusätzlich mit einem Eventualbegehren, dass die Rückführung für den Fall, dass das bundesgerichtliche Urteil nicht mehr vor Weihnachten gefällt werden könne, auf einen späteren, jedoch dem kantonalen Urteil möglichst nahe liegenden Zeitpunkt anzuordnen sei. Die Kindesvertreterin verlangt ferner die unentgeltliche Verbeiständung und Entschädigung aus der Gerichtskasse. Mit Schreiben vom 19. Dezember 2011 berichtete die Kindesvertreterin über ihr Telefonat mit D._, nachdem die Mutter dieses doch noch ermöglicht hatte. Mit Verfügung vom 23. Dezember 2011 wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Am 27. und 29. Dezember 2011 reichte die Mutter je eine Stellungnahme zu den Vernehmlassungen des Vaters und der Kindesvertreterin ein. Mit Schreiben vom 29. Dezember 2011 verwies der Vater auf eine Vereinbarung betreffend Verkauf der Liegenschaft in F._. Mit Schreiben vom 30. Dezember 2011 hat die Mutter hierzu Stellung genommen.

Erwägungen:
1. Von Amtes wegen sind die Fragen rund um das Eintreten, die Kognition des Bundesgerichts und das Novenverbot zu behandeln.
1.1 Bei Rückführungsentscheiden nach dem Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführungen (HKÜ, SR 0.211.230.02) geht es um die Regelung der Rechtshilfe zwischen den Vertragsstaaten (<ref-ruling> E. 2b S. 224), die in unmittelbarem Zusammenhang mit der Respektierung und Durchsetzung ausländischen Zivilrechts steht (Art. 72 Abs. 2 lit. b Ziff. 1 BGG; <ref-ruling>). Das Appellationsgericht hat als einzige kantonale Instanz entschieden (Art. 7 Abs. 1 des Bundesgesetzes über internationale Kindesentführung und die Haager Übereinkommen zum Schutz von Kindern und Erwachsenen, BG-KKE, SR 211.222.32), d.h. das Prinzip der double instance gilt in diesem Bereich nicht (<ref-law>). Die Beschwerdefrist von zehn Tagen ist eingehalten (<ref-law>). Die Beschwerde in Zivilsachen steht damit grundsätzlich offen.
1.2 Mit der Beschwerde in Zivilsachen kann nebst der Verletzung von Bundesrecht insbesondere die Verletzung von Staatsverträgen, vorliegend namentlich des HKÜ, geltend gemacht werden (Art. 95 lit. a und b BGG). Dem Bundesgericht steht diesbezüglich freie Kognition zu (<ref-law>).
Hingegen ist das Bundesgericht an den festgestellten Sachverhalt grundsätzlich gebunden (<ref-law>). Diesbezüglich kann einzig vorgebracht werden, er sei offensichtlich unrichtig festgestellt worden (<ref-law>), wobei "offensichtlich unrichtig" mit "willkürlich" gleichzusetzen ist (Botschaft, BBl 2001 IV 4338; <ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398), oder er beruhe auf einer anderen Rechtsverletzung im Sinn von <ref-law> (z.B. <ref-law> oder <ref-law>). Ausserdem muss in der Beschwerde aufgezeigt werden, inwiefern die Behebung der vorerwähnten Mängel für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2 S. 22).
Hierfür sowie für alle (anderen) Verfassungsrügen gilt das strenge Rügeprinzip (<ref-law>; <ref-ruling> E. 1.4.2 S. 255). Das bedeutet, dass das Bundesgericht nur klar und detailliert erhobene und soweit möglich belegte Rügen prüft, während es auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid nicht eintritt. Wird die Verletzung des Willkürverbots gerügt, reicht es sodann nicht aus, die Lage aus Sicht des Beschwerdeführers darzulegen und den davon abweichenden angefochtenen Entscheid als willkürlich zu bezeichnen; vielmehr ist im Einzelnen darzulegen, inwiefern das kantonale Gericht willkürlich entschieden haben soll und der angefochtene Entscheid deshalb an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246).
1.3 Mit der Beschwerde in Zivilsachen dürfen keine neuen Tatsachen und Beweismittel vorgebracht werden, es sei denn, erst der Entscheid der Vorinstanz habe dazu Anlass gegeben (<ref-law>). In der Beschwerde ist darzutun, inwiefern die Voraussetzung für eine nachträgliche Einreichung von Beweismitteln erfüllt sein soll (BGE <ref-ruling> E. 3 S. 395).
Diesen Anforderungen wird die Beschwerde, soweit mit ihr neue Beweismittel (Reisewarnung des deutschen auswärtigen Amtes für Südafrika sowie Unterlagen zum Gini-Koeffizienten, wonach sich aus den erheblichen Einkommensunterschieden eine hohe Kriminalitätsgefahr ergeben soll) vorgelegt werden, nicht gerecht, wird doch nicht dargelegt, wieso diese Dokumente nicht schon vor Appellationsgericht eingereicht wurden, obwohl die Mutter bereits dort geltend machte, in Südafrika sei es für die Kinder gefährlich.
2. Umstritten ist zunächst, ob die Mutter die Kinder widerrechtlich im Sinn von Art. 3 lit. a HKÜ in die Schweiz verbracht hat. Der Vater behauptet ein geteiltes Sorgerecht, während die Mutter behauptet, alleinige Obhutsinhaberin zu sein und insbesondere autonom den Aufenthalt der Kinder im Sinn von Art. 5 lit. a HKÜ bestimmen zu dürfen. Thema ist ferner, ob der Vater das Sorgerecht im Sinn von Art. 3 lit. b HKÜ tatsächlich ausgeübt hat.
2.1 Das Appellationsgericht hat mit Blick auf die Umschreibung der nach südafrikanischem Recht massgeblichen Sorgerechtsposition im Sinn von Art. 3 lit. a HKÜ auf die gestützt auf Art. 15 HKÜ ergangene Widerrechtlichkeitsbescheinigung der südafrikanischen Zentralbehörde vom 29. September 2011 verwiesen und erwogen, gemäss dem einschlägigen südafrikanischen Recht (Children's Act 38 aus dem Jahr 2005 [CA], Section 18 und 20) habe die Mutter angesichts der geteilten elterlichen Sorge die Kinder nicht ohne väterliche Zustimmung ins Ausland verbringen dürfen ("the mother was not entitled to remove the children from South Africa without the father's consent, by virtue of guardianship"; "it is clear that the children's mother has acted in breach of the father's custody rights and has acted wrongfully as envisaged by articles 3 and 5 of the 1980 Hague Convention on Child Abduction"). Das Appellationsgericht hat weiter erwogen, dies ergebe sich in klarer Weise auch aus den eingereichten Nachweisen zum südafrikanischen Recht: Gemäss Sect. 20 lit. a CA kämen dem mit der Kindsmutter verheirateten Kindsvater "full parental responsibilities and rights in respect of the child" zu, worunter gemäss Sect. 18 Abs. 2 lit. c CA auch das Recht falle, als "guardian of the child" zu handeln. Als solcher habe der Vater gemäss Sect. 18 Abs. 3 lit. c/iii CA auch seine Zustimmung für eine Ausreise aus der Republik Südafrika zu erteilen. Soweit diese Kompetenzen, wie vorliegend, beiden Elternteilen zustünden (Sect. 19 und 20 CA), hätten sie gemeinsam zu handeln (Sect. 18 Abs. 4 CA).
2.2 Soweit die Mutter vorbringt, der Vater habe im Zusammenhang mit der Widerrechtlichkeitsbescheinigung gegenüber der südafrikanischen Zentralbehörde falsche Angaben gemacht (in Wahrheit habe er gar nicht mehr mit den Kindern zusammengelebt, sondern sei er auslandsabwesend gewesen; er habe unrichtig behauptet, die Kinder würden kein Deutsch sprechen, obwohl sie sich gut in Schweizerdeutsch verständigen könnten; in der letzten Zeit seien viele Schulden entstanden), so ist nicht ersichtlich, inwiefern dies für die Frage der Widerrechtlichkeit der Sorgerechtsverletzung und damit für den Verfahrensausgang relevant sein könnte: Entscheidend ist nach südafrikanischem Recht bzw. nach dem Children's Act, dass dem verheirateten Vater "full parental responsibilities and rights in respect of the child" zukommen und er insbesondere als "guardian of the child" handeln kann, womit die Mutter nicht über das alleinige Aufenthaltsbestimmungsrecht für die Kinder im Sinn von Art. 5 lit. a HKÜ verfügt. Diese aus dem Children's Act klar hervorgehende nationale Rechtslage verschafft dem Vater eine genügende Sorgerechtsposition (rights of custody) im Sinn von Art. 3 lit. a HKÜ.
Nicht zielführend ist die pauschale und unbelegte Behauptung, ein "Act" (vorliegend der Children's Act) habe im südafrikanischen Rechtssystem nicht die gleiche Wirkung wie ein Gesetz, sondern diene nur als Grundlage für die effektive Rechtsfindung, die in einem auf den Einzelfall ausgerichteten Verfahren stattfinde, wird doch in der Beschwerde ein das statutary law verdrängendes abweichendes case law nicht ansatzweise dargetan.
2.3 Mit Blick auf Art. 3 lit. b HKÜ und das Vorbringen der Mutter, der Vater habe sich gar nicht um die Kinder gekümmert, hat das Appellationsgericht erwogen, die Eltern hätten die ersten 18 Monate mit den Kindern zusammen gewohnt. Anschliessend habe der Vater in Johannesburg gewohnt und sei wöchentlich zwischen dort und dem Familienwohnsitz gependelt. Bei seinem Arbeitsaufenthalt in Deutschland habe er die Ferien und Überstunden bei der Familie in Südafrika verbracht. Nach seiner Rückkehr nach Südafrika im April 2011 habe er sich aufgrund der ehelichen Spannungen bei seiner neuen Partnerin und deren Sohn in Johannesburg niedergelassen. Er habe die Kinder aber weiterhin regelmässig besucht, nach seinen Angaben alle zwei Wochen von Freitagabend bis Montagmorgen sowie während der Ferien, nach Angaben der Mutter "etwa einmal im Monat". Diese Besuche und das Verbringen der Ferien fielen unter die weit gefasste Ausübung des Sorgerechts und hätten regelmässig stattgefunden, weshalb das Sorgerecht im Sinn von Art. 3 lit. b HKÜ tatsächlich ausgeübt worden sei. Sodann habe der Vater auch sofort gerichtliche Schritte eingeleitet, nachdem die Mutter die Kinder heimlich aus Südafrika verbracht habe.
Die tatsächliche Ausübung des Sorgerechts durch den Vater im Sinn von Art. 3 lit. b HKÜ wird vor Bundesgericht nicht mehr substanziiert bestritten und aufgrund des vorinstanzlich festgestellten Sachverhaltes muss sie auch bejaht werden, ist sie doch in einem weiten Sinn zu verstehen und in der Regel gegeben, wenn sich der Sorgerechtsinhaber um die Rückgabe der Kinder bemüht und er regelmässigen Kontakt mit ihnen hatte (<ref-ruling> E. 2.2.1 S. 699 mit Hinweisen auf die Literatur).
2.4 Wie bereits das Appellationsgericht zutreffend festgehalten hat, sind die finanziellen Verhältnisse der Parteien bzw. die Erwerbstätigkeit des Vaters für die Frage des widerrechtlichen Verbringens ebenso wenig relevant wie die Sicherheitssituation in Südafrika, weshalb auf diese Punkte an dieser Stelle nicht näher einzugehen ist. Sie können eine Relevanz im Zusammenhang mit der Gefahr im Sinn von Art. 13 Abs. 1 lit. b HKÜ haben, worauf im betreffenden Zusammenhang zurückzukommen sein wird.
3. Liegt nach dem Gesagten ein widerrechtliches Verbringen der Kinder vor, ist gestützt auf Art. 12 Abs. 1 HKÜ die sofortige Rückführung der Kinder anzuordnen. Von einer Rückführung kann einzig dann abgesehen werden, wenn ihr ein Ausschlussgrund entgegensteht. Einen solchen ruft die Mutter mit Art. 13 Abs. 1 lit. b HKÜ an, nach welcher Norm der ersuchte Staat nicht zur Rückführung verpflichtet ist, wenn der sich der Rückführung widersetzende Teil nachweist, dass die Rückgabe mit der schwerwiegenden Gefahr eines körperlichen oder seelischen Schadens für die Kinder verbunden ist oder diese auf andere Weise in eine unzumutbare Lage gebracht werden.
3.1 Nach der im Urteil 5A_913/2010 vom 4. Februar 2011 E. 5.1 zusammengefassten bundesgerichtlichen Rechtsprechung liegt eine schwerwiegende Gefahr körperlicher oder seelischer Schädigung im Sinn von Art. 13 Abs. 1 lit. b HKÜ zum Beispiel bei einer Rückführung in ein Kriegs- oder Seuchengebiet vor, aber auch, wenn ernsthaft zu befürchten ist, dass das Kind nach der Rückgabe misshandelt oder missbraucht wird und nicht zu erwarten ist, dass die zuständigen Behörden des Herkunftsstaates gegen die Gefährdung erfolgreich einschreiten (Urteile 5A_105/2009 vom 16. April 2009 E. 3.3; 5A_764/2009 vom 11. Januar 2010 E. 4.1; 5A_436/2010 vom 8. Juli 2010 E. 4.2). Keine schwerwiegende Gefahr seelischer Schädigung begründen anfängliche Sprach- und Reintegrationsschwierigkeiten, wie sie sich bei Kindern ab einem gewissen Alter mehr oder weniger zwangsläufig ergeben (<ref-ruling> E. 3 S. 535). Sodann geht es im Rückführungsverfahren nicht um materiell-rechtliche Fragen, wie sie für die Zuteilung des Sorgerechts massgebend sind, namentlich bei welchem Elternteil oder in welchem Land die Kinder besser aufgehoben oder welcher Elternteil zur Erziehung und Betreuung besser geeignet wäre (<ref-ruling> E. 5.3 S. 341; <ref-ruling> E. 2.4 S. 149); der Entscheid darüber ist nach dem System des HKÜ dem Sachrichter des Herkunftsstaates vorbehalten (vgl. Art. 16 und 19 HKÜ). Was die Trennung von Mutter und Kind im Speziellen anbelangt, gilt es zunächst zu beachten, dass sich das Kriterium der Unzumutbarkeit der Rückkehr in den Herkunftsstaat in erster Linie auf das Kind selbst bezieht. Das heisst, dass es unter Umständen zu einer Trennung zwischen den Kindern und der Hauptbezugsperson kommen kann, was aber nach der bundesgerichtlichen Rechtsprechung und der herrschenden Lehre für sich allein noch keinen Versagensgrund für die Rückführung bildet (<ref-ruling> E. 3 S. 535; SCHMID, Neuere Entwicklungen im Bereich der internationalen Kindesentführungen, in: AJP 2002, S. 1333; BACH/GILDENAST, Internationale Kindesentführung, Bielefeld 1999, Rz. 131; KUHN, Ihr Kinderlein bleibet, so bleibet doch all, in: AJP 1997, S. 1099). Anders verhält es sich allerdings bei Säuglingen; hier bringt eine Trennung von der Mutter das Kind in jedem Fall in eine unzumutbare Lage (BUCHER, L'enfant en droit international privé, Basel 2003, Rz. 471; RASELLI/HAUSAMMANN/MÖCKLI/URWYLER, Ausländische Kinder sowie andere Angehörige, in: Ausländerrecht, Basel 2008, N. 16.164). Was das Zusammenspiel zwischen Grundsatz (sofortige Rückführung) und Ausnahme anbelangt, besteht in der Rechtsprechung ein allgemeiner Konsens, wonach die Ausschlussgründe eng auszulegen und bei Art. 13 Abs. 1 lit. b HKÜ nur wirkliche Gefahren zu berücksichtigen sind (für Deutschland: Bundesverfassungsgericht BvR 1206/98 vom 29. Oktober 1998, Rz. 48; für Österreich: Oberster Gerichtshof Nr. 5Ob47/09m vom 12. Mai 2009; Nr. 2Ob103/09z vom 16. Juli 2009; für die Rechtsprechung in anderen HKÜ-Staaten vgl. die Nachweise bei BEAUMONT/ MCELEAVY, The Hague Convention on International Child Abduction, Oxford 1999/2004, S. 138 ff., insb. S. 141 ff.; PIRRUNG, in: von Staudingers Kommentar zum BGB, Berlin 2009, Vorbem zu Art. 19 EG/BGB, D 71; SIEHR, in: Münchener Kommentar zum Bürgerlichen Gesetzbuch, Band 10, München 2005, Art. 21 Anh. II, Rz. 73; ZÜRCHER, Kindesentführung und Kindesinteressen, Zürich 2005, S. 100 ff.; PAPE, Internationale Kindesentführung, Frankfurt 2010, S. 77 f.).
3.2 Soweit die Mutter im Zusammenhang mit den Ausschlussgründen gemäss Art. 13 Abs. 1 lit. b HKÜ eine Verletzung des - primär im materiellen Erkenntnisverfahren zum Tragen kommenden - <ref-law> rügt, verkennt sie, dass sie nach dem klaren Wortlaut von Art. 13 Abs. 1 HKÜ die Beweislast für die eine Rückführung ausschliessenden Sachverhaltselemente trägt. Es liegt deshalb in erster Linie an ihr, die rechtserheblichen Tatsachen und Beweismittel zu nennen; daran ändert der Untersuchungsgrundsatz nichts (vgl. <ref-ruling> E. 3.2.1 S. 413; <ref-ruling> E. 5.4 S. 511). Er bedeutet einzig, dass das Gericht auch von sich aus Elemente abklären kann. Vorliegend ist der Sachverhalt mit Bezug auf die schwerwiegende Gefahr eines körperlichen oder seelischen Schadens für die Kinder in hinreichender Weise liquid, wie die nachfolgenden Erwägungen zeigen, weshalb das Eventualbegehren um Rückweisung zu weiterer Sachverhaltsabklärung abzuweisen ist.
3.3 Nach den kantonalen Sachverhaltsfeststellungen haben die beiden heute knapp 8- und 10-jährigen Kinder quasi ihr ganzes Leben in Südafrika verbracht, wo sie auch zur Schule gegangen sind und diverse sportliche Aktivitäten verfolgt haben, wo sie ihre Freunde haben, mit welchen sie soweit möglich den Kontakt zu behalten versuchen, und wo sie auch Haustiere hielten. Beide Kinder haben angegeben, ihren Vater, ihre Freunde und ihre Tiere zu vermissen (Kinderanhörung und Angaben der Kindesvertreterin). C._ empfand ihren Abschied von Südafrika sehr traurig, konnte sie sich doch nicht einmal von ihrem Vater, den Freunden und dem Hund verabschieden. Beide Kinder sprechen Deutsch, Englisch und Afrikaans. Sie haben zu beiden Elternteilen ein gutes Verhältnis. Die Kinder haben keinen anderen Bezug zur Schweiz, als dass sie hier einzelne Ferienaufenthalte verbracht haben.
3.4 Die Mutter behauptet jedoch, in Südafrika sei es extrem gefährlich (Raub, Entführung, Mord, Vergewaltigung) und bei einem Wohnen ausserhalb von "gated communities" drohten den Kindern konkrete Gefahren an Leib und Leben. Diese Vorbringen sind offensichtlich Schutzbehauptungen, die an den Realitäten vorbeigehen: Die Familie hatte sich seinerzeit zur Auswanderung entschlossen und in Südafrika ein gutes und sicheres Leben verbracht. Beide Elternteile wissen aufgrund ihrer langjährigen Zeit vor Ort, in welchen Gegenden es gefährlich ist bzw. wohin man sich besser nicht begeben sollte. Die Kinder selbst haben sich bei der Anhörung mit Begeisterung über das Leben in Südafrika geäussert.
Was die konkrete Lebenssituation anbelangt, so trifft es zu, dass die Mutter mit den Kindern vorerst nicht im gemeinsamen Haus in Somerset West leben könnte, weil der Vater dieses nach der heimlichen Abreise der Mutter für ein Jahr vermietete, um es nicht brach liegen zu lassen. Das heisst, dass in Somerset West zumindest vorübergehend eine andere Unterkunft angemietet werden müsste, wie der Vater vor dem Appellationsgericht ausführte. Inwiefern dadurch eine konkrete Gefahr für die Kinder drohen soll, ist unerfindlich, zumal der Vater im kantonalen Verfahren diesbezüglich Hand geboten hat. Sodann ging die Mutter in Südafrika auch diversen beruflichen Aktivitäten nach und insbesondere verfügt die Familie über grössere gemeinsame Vermögenswerte (Haus in F._ im Wert von ca. EUR 850'000.--, welches die Parteien verkaufen wollen, sowie das besagte Haus in Somerset West im Wert von ca. Rand 3,9 Mio.). Auch wenn angesichts der aktuellen Einkommensverhältnisse möglicherweise nicht mehr das bis anhin geführte Luxusleben (grosse Autos, Hausangestellte, u.ä. wie es sich aus dem aktenkundigen E-Mail-Verkehr ergibt) möglich sein sollte, so geht es jedenfalls weder in Kapstadt bzw. Somerset West noch in Johannesburg darum, in einem heruntergekommenen und kriminellen Township zu leben, wie die Mutter dies glauben machen will.
Was sodann die Schulsituation anbelangt, wurde die Privatschule unmittelbar vor der Abreise provisorisch gekündigt, was allerdings zwischen den Eltern seit längerer Zeit abgesprochen bzw. ins Auge gefasst worden war. Inwiefern es für die Kinder unzumutbar sein sollte, in eine öffentliche bzw. halbprivate (ebenfalls zu bezahlende, aber günstigere) Schule zu gehen, ist nicht zu sehen, umso mehr als nach den kantonalen Feststellungen offenbar Freunde der Kinder dort bereits problemlos eingeschult sind. Wenn die Mutter sinngemäss vorbringt, die definitive Klärung der Schulsituation in Südafrika sei eine Rückführungsvoraussetzung, übergeht sie, dass die Schulsituation gerade von dem Rückreisemodalitäten abhängt, und zwar namentlich davon, ob sie selbst mit den Kindern zurückkehren würde und ob sie diesfalls wieder in oder in der Nähe von Somerset West leben würden, oder ob die Mutter ihre vagen Andeutungen wahr machen und in der Schweiz bleiben würde, so dass die Kinder fortan beim Vater leben würden.
Selbst wenn der (letztlich aber von keinem der beiden Elternteile ernsthaft diskutierte) Fall eintreten würde, dass die Mutter in der Schweiz bleiben sollte, wäre keine schwerwiegende Gefahr eines körperlichen oder seelischen Schadens für die Kinder ersichtlich: Es würde nicht zu einer von <ref-law> verpönten Fremdplatzierung der Kinder kommen, sondern diese würden, wie vom Vater vor Appellationsgericht für den betreffenden Fall angeboten, bei ihm und seiner Partnerin in Johannesburg leben, was nach den kantonalen Feststellungen zumindest für C._ ebenfalls ein vertrautes Umfeld darstellt. Die Mutter macht in der Beschwerde nirgends geltend, dass dies eine unhaltbare Situation wäre, und solches wäre denn auch nicht ersichtlich, da beide Kinder eine gute Beziehung zum Vater haben und sie sich anlässlich der Anhörung und gegenüber der Kindesvertreterin positiv zu einer Rückkehr nach Südafrika äusserten. Im Übrigen arbeitet die Mutter in der Schweiz, so dass sie nicht anders als der Vater auf eine entsprechende Drittbetreuung der Kinder angewiesen ist.
Was schliesslich das Erwerbseinkommen des Vaters anbelangt, kritisiert die Mutter, dass nicht genügend Abklärungen betreffend die Anstellung bei der (offenbar dem Sohn der Lebenspartnerin des Beschwerdeführers gehörenden) Firma "G._" angestellt worden seien. Wie die Modalitäten im Einzelnen aussehen (ob die Firma in der Rechtsform der AG oder GmbH konstituiert und an welcher Adresse sie domiziliert ist, etc.) musste vorliegend nicht im Detail überprüft werden, wurden doch Gehaltsabrechnungen vorgelegt und hat sich der Vater im Übrigen immer um ein genügendes Familieneinkommen bemüht; es wurde denn auch nie behauptet, dass er nicht arbeitswillig wäre. Zudem verfügen die Ehegatten über erhebliche Vermögenswerte. Vor diesem Hintergrund ist im Zusammenhang mit der Erwerbstätigkeit des Vaters und einer Rückführung keine schwerwiegende Gefahr eines körperlichen oder seelischen Schadens oder anderweitig eine unzumutbare Lage für die Kinder - und einzig darum geht es beim Ausschlussgrund von Art. 13 Abs. 1 lit. b HKÜ - ersichtlich.
Insgesamt ergibt sich, dass nicht dargetan ist, inwiefern die Rückkehr nach Südafrika für die Kinder mit einer schwerwiegenden Gefahr eines körperlichen oder seelischen Schadens verbunden sein oder diese auf andere Weise in eine unzumutbare Lage bringen soll bzw. inwiefern diesem rechtlichen Schluss eine in willkürlicher Weise festgestellte Sachverhaltsbasis zugrunde liegen würde.
3.5 Abschliessend wirft die Mutter dem Vater Rechtsmissbrauch im Sinn von <ref-law> vor, weil er in Südafrika bleiben wolle. Dieses Vorbringen hat indes nichts mit dem Ausschlussgrund von Art. 13 Abs. 1 lit. b HKÜ zu tun. Abgesehen davon beruhte die seinerzeitige Auswanderung auf gemeinsamer Familienplanung und haben beide Kinder quasi ihr gesamtes bisheriges Leben in Südafrika verbracht.
4. Subeventualiter verlangt die Beschwerdeführerin, dass die Rückführung mit diversen Auflagen (Verpflichtung des Vaters zur Anmeldung der Kinder an einer Schule in der Region Somerset West; Bezahlung der Schulkosten für zwei Jahre; Bezahlung des Mietzinsdepots und einer Wohnung in der Region Somerset West) zu verbinden sei.
Wie das Appellationsgericht zutreffend ausgeführt hat, sieht das HKÜ nicht vor, dass die Rückführung an solche Auflagen geknüpft werden darf, wenn die Rückführungsvoraussetzungen gegeben sind; es würde mithin an einer Rechtsgrundlage für entsprechende Anordnungen durch den Rückführungsrichter fehlen, zumal dieser für die Regelung der materiellen Belange wie namentlich des Sorgerechts und der damit einhergehenden finanziellen Modalitäten nicht zuständig ist. Indes sind Konstellationen denkbar, wo ohne bestimmte Garantien von einer Unzumutbarkeit für das Kind im Sinn von Art. 13 Abs. 1 lit. b HKÜ auszugehen ist, während finanzielle oder anderweitige Zusagen (Unterbringung, Schule, Betreuung, etc.) des Gesuchstellers die Rückführung als für das Kind zumutbar erscheinen lassen. Diesfalls werden die vorerwähnten Rückführungsvoraussetzungen (nämlich das Fehlen eines Ausschlussgrundes) aber überhaupt erst durch die betreffenden Garantien geschaffen, und es versteht sich von selbst, dass in solchen Fällen die Rückführung an die betreffenden Bedingungen geknüpft werden darf. So wurde etwa die Rückführung eines muttergebundenen Kleinkindes davon abhängig gemacht, dass es im Zuge der Rückführung und bis zu einem allenfalls anderslautenden Entscheid des Sachrichters nicht zu einer Trennung zwischen Mutter und Kind kommen würde, weil das Kind damit in eine unzumutbare Lage im Sinn von Art. 13 Abs. 1 lit. b HKÜ gebracht worden wäre (Einreisemöglichkeit der Mutter, keine Inhaftierung der Mutter, vgl. Urteil 5A_105/2009 vom 16. April 2009 E. 3).
Der vorliegende Fall ist anders gelagert: Wie in E. 3.4 ausgeführt, liegen auch ohne spezielle Garantien keine schwerwiegenden Gefahren für die Kinder im Sinn von Art. 13 Abs. 1 lit. b HKÜ vor. Im Übrigen ist zu erwähnen, dass die Mutter in ihrem Subeventualbegehren letztlich nichts anders verlangt, als was der Vater in der vor Appellationsgericht abgeschlossenen Vereinbarung, welche von der Mutter in der Folge freilich widerrufen wurde, zugestanden hatte: Die Parteien hatten dort die Rückführung der Kinder nach Südafrika vereinbart und der Vater verpflichtete sich, als Unterhalt an Frau und Kinder zwei Drittel seines Nettoeinkommens zu bezahlen sowie eine Bürgschaft für die Miete einer angemessenen Familienwohnung zu leisten. Es finden sich keine Hinweise in den Akten, dass der Vater, nur weil die Mutter diese Vereinbarung widerrufen hat, nicht mehr bereit wäre, angemessene Unterhaltszahlungen zu leisten (der Vater spricht in der Vernehmlassung, S. 7 oben, weiterhin von einer Vereinbarung, die erzielt werden sollte), und andernfalls könnten solche im Herkunftsstaat offensichtlich auch gerichtlich eingefordert werden, wie der Vater festhält (Vernehmlassung, S. 6 unten). Im Übrigen darf davon ausgegangen werden, dass die Mutter auch in Südafrika wieder beruflichen Aktivitäten nachgehen kann; sie behauptet jedenfalls nichts anderes, sondern beschränkt sich auf die Aussage, dort keine Arbeit zu haben, was sich aber logisch aus dem Umstand ergibt, dass sie sich momentan in der Schweiz aufhält und hier arbeitstätig ist.
5. Zusammenfassend ergibt sich, dass die Beschwerde in Zivilsachen abzuweisen ist, soweit auf sie eingetreten werden kann. Weil die aufschiebende Wirkung erteilt worden ist, sind indes die im angefochtenen Urteil angesetzten Zeitpunkte bzw. Fristen zur freiwilligen Rückführung und betreffend Zwangsvollstreckung neu festzulegen.
6. Grundsätzlich ist das Rückführungsverfahren auch vor Bundesgericht kostenlos (Art. 26 Abs. 2 HKÜ und <ref-law>). Südafrika hat indes einen Vorbehalt angebracht, wonach die Verfahrens- und Parteikosten nur im Rahmen des Systems der unentgeltlichen Rechtspflege übernommen werden (Art. 26 Abs. 3 i.V.m. Art. 42 HEntfÜ). Die Schweiz wendet diesfalls das Prinzip der Gegenseitigkeit an (Art. 21 Abs. 1 lit. b des Wiener Übereinkommens über das Recht der Verträge, SR 0.111) und gewährt Kostenfreiheit nur im Rahmen der nationalen unentgeltlichen Rechtspflege. Angesichts des (Brutto-)Einkommens der Mutter von Fr. 8'000.-- und der erheblichen Vermögenswerte (die Parteien verfügen in F._ über eine gemeinsame Liegenschaft mit einem geschätzten Wert von EUR 850'000.-- und in Südafrika über eine gemeinsame Liegenschaft mit einem geschätzten Wert von Rand 3,9 Mio.) ist ihr Gesuch um unentgeltliche Rechtspflege auch für das bundesgerichtliche Verfahren mangels Prozessarmut abzuweisen (<ref-law>). Die Mutter wird damit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG), dies auch für die gerichtlich bestellte Vertreterin der Kinder, weil die betreffenden Kosten als Gerichtskosten gelten (vgl. zur Publikation bestimmtes Urteil 5A_674/2011 vom 15. Dezember 2011 E. 6).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
Die freiwillige Rückführung im Sinn von Abs. 1 des Dispositivs des angefochtenen Urteils hat bis spätestens 29. Februar 2012 stattzufinden. Eine allfällige Zwangsvollstreckung im Sinn von Abs. 2 des Dispositivs des angefochtenen Urteils ist innert 60 Tagen seit Zustellung des vorliegenden Urteils durchzuführen.
2. Das Gesuch der Beschwerdeführerin um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'763.-- (inkl. Honorar für die Kindesvertreterin) werden der Beschwerdeführerin auferlegt.
4. Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'344.-- zu entschädigen.
5. Advokatin Esther Wyss Sisti wird aus der Bundesgerichtskasse mit Fr. 763.-- entschädigt.
6. Dieses Urteil wird den Parteien sowie der Vertreterin von C._ und D._, dem Appellationsgerichtspräsidenten des Kantons Basel-Stadt, dem Departement Volkswirtschaft und Inneres des Kantons Aargau als Vollstreckungsbehörde sowie der Zentralbehörde schriftlich mitgeteilt.
Lausanne, 13. Januar 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Möckli