Sachverhalt:
A. Y._ ist das einzige Kind der Ehegatten A._ und B._, alle Staatsangehörige von C._ mit Wohnsitz in C._. Am 25. Oktober 1982 eröffneten die Eltern bei der Bank X._, mit Sitz in Basel, ein Konto und ein Depot. Im Jahre 1987 verstarb B._ und im Jahre 2002 A._. Bereits am 26. November 1997 erhob Y._ beim Zivilgericht Basel-Stadt Klage gegen die Bank X._ auf Auskunftserteilung betreffend der Vermögenswerte ihrer Eltern, welche mit Urteil vom 18. Januar 2001 abgewiesen wurde. Mit Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 26. März 2004 wurde dieses Urteil des Zivilgerichts aufgehoben und die Bank X._ unter Androhung der Ungehorsamsstrafe (<ref-law>) verurteilt, Y._ schriftlich mit den banküblichen Belegen (lückenlose Kontoauszüge, Zahlungsaufträge, Gutschriftenanzeigen usw.) vollständigen Aufschluss über die Vermögenswerte ihrer Eltern zu erteilen über (Dispositiv-Ziffer 1):
"a) per Stichtag 26. November 1987: sämtliche Wertschriften- und Edelmetall-Depots, Konten, Schrankfächer und sämtliche andere Vermögenswerte irgendwelcher Art,
- welche, sei es einzeln oder gemeinsam, sei es im eigenen Namen, sei es unter Verwendung eines Decknamens oder von Nummern, von Herrn A._ und/oder seiner Ehefrau B._ hinterlegt bzw. errichtet wurden;
- welche von der Beklagten oder sonstigen Dritten treuhänderisch für Rechnung von Herrn A._ und/oder Frau B._ gehalten werden;
b) den Zeitraum vor dem Stichtag und ab Eröffnung des jeweiligen Depots, Kontos usw.:
- die Entwicklung der genannten Depots, Konten und sonstigen Vermögenswerte gemäss lit. a, insbesondere was Vermögensabflüsse und Vermögenszuflüsse irgendwelcher Art betrifft, auch wenn die entsprechenden Depots, Konti usw. am Stichtag nicht mehr bestanden haben sollten;
- insbesondere die auf der Liste vom 6. Februar 1990 aufgeführten Auszahlungen, und zwar unter namentlicher Angabe der Empfänger;
- Öffnungen von Schrankfächern gemäss lit. a;
c) den Zeitraum nach dem Stichtag:
- sämtliche Erträgnisse und sonstigen Vermögenszuflüsse und sämtliche Verfügungen über die Vermögenswerte gemäss lit. a;
- Öffnungen von Schrankfächern gemäss lit. a;
und zwar für diejenigen Vermögenswerte, die Herrn A._ bzw. der Klägerin am 20. Mai 1988 zugewiesen wurden, bis zu diesem Tage und für andere Vermögenswerte ohne zeitliche Begrenzung."
B. Mit Eingabe vom 7. September 2006 stellte Y._ beim Zivilgericht Antrag auf Erlass eines Befehls zur Vollstreckung des Urteils des Appellationsgerichts vom 26. März 2004. Mit Exekutionsbefehl Nr. 1 vom 3. Oktober 2006 hiess das Zivilgericht das Vollstreckungsbegehren gut und wies die Bank X._ an, Y._ entsprechend dem zu vollstreckenden Urteil vollständigen Aufschluss zu erteilen; das Vollstreckungsbegehren wurde insoweit abgewiesen, als die anbegehrte Beantwortung von Fragen nicht Inhalt des Dispositivs des zu vollstreckenden Urteils war.
C. Auf Einsprache der Parteien hin befahl das Appellationsgericht am 1. Juli 2008 der Bank X._, Y._ entsprechend dem zu vollstreckenden Urteil vollständigen Aufschluss über die Vermögenswerte ihrer Eltern zu erteilen. Zudem seien die von Y._ (im Vollstreckungsgesuch) gestellten Fragen zu beantworten.
D. Mit Eingabe vom 1. Dezember 2008 führt die Bank X._ Beschwerde in Zivilsachen und subsidiäre Verfassungsbeschwerde. Die Beschwerdeführerin beantragt dem Bundesgericht, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 1. Juli 2008 und in Gutheissung ihrer Einsprache den Exekutionsbefehl Nr. 1 des Zivilgerichts Basel-Stadt vom 3. Oktober 2006 aufzuheben. Eventualiter sei die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Y._ als Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Appellationsgericht schliesst auf Abweisung der Beschwerde.
Mit Präsidialverfügung vom 8. Januar 2009 wurde der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Der angefochtene Entscheid erging im Verfahren zur Vollstreckung des Urteils des Appellationsgerichts des Kantons Basel-Stadt vom 26. März 2004, mit welchem gestützt auf Vertragsrecht die Pflicht zur Auskunftserteilung festgesetzt wurde. Entscheide über die Vollstreckung von Entscheiden in Zivilsachen unterliegen der Beschwerde in Zivilsachen (Art. 72 Abs. 2 lit. b Ziff. 1 BGG).
1.2 Das zu vollstreckende Urteil ist in einem Streit um einen Informationsanspruch ergangen und stellt eine vermögensrechtliche Streitigkeit dar, unabhängig davon, ob der Anspruch vertraglich (Urteil 4A_398/2008 vom 18. Dezember 2008 E. 1.4.2, nicht publ. in: <ref-ruling>) oder erbrechtlich (<ref-ruling> E. 1b/cc S. 398) begründet ist. Entgegen <ref-law> enthält das angefochtene Urteil keine Streitwertangabe. Nach der Rechtsprechung kann bei Auskunftsbegehren von einer exakten Bezifferung des Streitwertes abgesehen werden (<ref-ruling> E. 1b/cc S. 398; Urteil 5C.157/2003 vom 22. Januar 2004 E. 3.2, in: SJ 2004 I S. 479). In Anbetracht des Umfangs des Auskunftsgesuchs ist im vorliegenden Vollstreckungsverfahren die gesetzliche Streitwertgrenze von Fr. 30'000.-- erreicht (<ref-law>).
1.3 Gegen das Urteil des Appellationsgerichts ist nach dem kantonalen Recht kein Rechtsmittel gegeben (vgl. Dritter Abschnitt der ZPO/BS). Das obere Gericht hat als letzte kantonale Instanz entschieden (Art. 75 Abs. 1 und 2 BGG).
1.4 Gemäss <ref-law>/BS entscheidet der Richter, welcher das Sachurteil gefällt hat, über Einwände, welche gegen den (im Einparteienverfahren erlassenen) Exekutionsbefehl des Zivilgerichtspräsidenten (<ref-law>/BS) erhoben werden. Im vorliegenden Fall wurde das Sachurteil vom Appellationsgericht gefällt. Ob der Entscheid über die Einwände gegen die Vollstreckung - d.h. der angefochtene Entscheid - vom Appellationsgericht als Rechtsmittelbehörde gemäss <ref-law> oder (wie die Beschwerdeführerin meint) als Erstinstanz gefällt worden ist, braucht nicht weiter erörtert zu werden. Im Rahmen der noch nicht abgelaufenen Übergangsfrist von <ref-law> sind kantonale Gerichte, die (abgesehen von den in Art. 75 Abs. 2 lit. a-c BGG angeführten Fällen) als einzige kantonale Instanzen entscheiden, noch zulässig.
1.5 Der angefochtene Entscheid schliesst das (Vollstreckungs-)Verfahren ab (<ref-law>). Die Beschwerde in Zivilsachen ist grundsätzlich zulässig.
1.6 Beim zu vollstreckenden Sachentscheid handelt es sich nicht um eine vorsorgliche Massnahme, so dass die Beschwerdegründe gegen den Entscheid über die Vollstreckung nicht beschränkt sind (vgl. <ref-law>; Urteil 5A_627/2007 vom 28. Februar 2008 E.1), und es kann die Verletzung von u.a. Bundes- und Völkerrecht und kantonalen verfassungsmässigen Rechten gerügt werden (Art. 95 lit. a-c BGG). In der Beschwerdebegründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Die Verletzung von verfassungsmässigen Rechten ist in der Beschwerdeschrift vorzubringen und zu begründen (<ref-law>), wobei das Rügeprinzip gilt (<ref-ruling> E. 2 S. 591).
1.7 Da die Beschwerde in Zivilsachen zulässig ist, wird die Eingabe als solche, nicht als Verfassungsbeschwerde entgegengenommen (<ref-law>).
2. Das Appellationsgericht hat erwogen, in der Realvollstreckung könne der Vollstreckungsgegner gemäss <ref-law>/BS mittels Urkunden einwenden, die Verbindlichkeit sei seit Erlass des Urteils erfüllt worden. Im Vollstreckungsverfahren als Summarverfahren komme eine Befragung von F._ und G._, der eine Mitglied des Verwaltungsrates und Direktor, der andere Direktor der Beschwerdeführerin, nicht in Betracht. Mit der Einrede der Erfüllung könne die Beschwerdeführerin als Vollstreckungsgegnerin nicht durchdringen. Es sei ausgeschlossen, dass die Beschwerdeführerin als Bank Auszahlungen und Geldüberweisungen vornehme, ohne dass sie sich hierfür Quittungen geben lasse und/oder interne Belege anfertige und aufbewahre, auch wenn sich auf dem betreffenden Konto Schwarzgeld befinde. Die Beschwerdeführerin sei nach wie vor verpflichtet, der Beschwerdegegnerin die Herkunft der einbezahlten und die Destination der ausbezahlten Gelder bekannt zu geben. Im zu vollstreckenden Urteil (vom 26. März 2004) sei die grundsätzlich umfassende Auskunftspflicht festgestellt worden. Die blosse, unbewiesene Behauptung, über H._ sei im Auftrag der Eheleute A._/B._ ein Geldwechselsystem betrieben worden und der Auftrag der Bank sei in der Auszahlung bzw. Überweisung von Geld an H._ erschöpft, stehe der Vollstreckung nicht entgegen. Was die Beschwerdeführerin im Weiteren gegen die Auskunftspflicht im Prozess nicht eingewendet habe, könne sie im Vollstreckungsverfahren nicht nachholen. Die Fragen gemäss Katalog der Beschwerdegegnerin, welche diese gestützt auf gewisse ausgehändigte Unterlagen gestellt habe, würden vom Dispositiv des zu vollstreckenden Urteils, welches zu "vollständigem Aufschluss" verpflichte, erfasst. Nach Auffassung des Appellationsgerichts sind die Einwände der Beschwerdeführerin unbehelflich und ist das Urteil vom 26. März 2004 zu vollstrecken.
3. Die Beschwerdeführerin wirft der Vorinstanz im Wesentlichen vor, die von ihr anerbotene Befragung von F._ und G._ zu Unrecht verweigert zu haben. Die Beschränkung der Einwände im Vollstreckungsverfahren auf Urkunden verletze das Gebot der freien Prüfung des Sachverhalts gemäss <ref-law>, sei überspitzt formalistisch (<ref-law>) und im kantonalen Verfahren nicht vorgesehen. Sie verstosse zudem gegen den Vorrang des Bundesrechts (<ref-law>) und das Recht auf den Beweis bzw. den Gehörsanspruch (<ref-law>, <ref-law>). Weiter nehme die Vorinstanz willkürlich (<ref-law>) an, die Einrede der Erfüllung bereits im Hauptverfahren thematisieren zu müssen.
3.1 Die Regelung und Durchführung der Zwangsvollstreckung von Urteilen, die nicht auf Geldzahlung oder Sicherheitsleistung, sondern auf andere Leistungen gerichtet sind, steht in der Kompetenz der Kantone (vgl. <ref-law>). Nach dem Recht des Kantons Basel-Stadt kann der Vollstreckungsgegner in der Regel nur einwenden, dass der durchzusetzende Anspruch infolge von Tatsachen, die nach Erlass des Urteils eingetreten sind, untergegangen sei oder der Fälligkeit entbehre, praktisch also Tilgung, Erlass, Stundung und Verjährung (<ref-law>/BS; Staehelin/Sutter, Zivilprozessrecht nach den Gesetzen der Kantone Basel-Stadt und Basel-Landschaft unter Einbezug des Bundesrechts, 1992, § 25 Rz. 8). Nach der Lehre zum kantonalen Recht ist das Verfahren vor dem Vollstreckungsrichter summarisch ausgestaltet; im Sinne der Beweismittelbeschränkung sind in der Regel nur Urkunden zugelassen (STAEHELIN/SUTTER, a.a.O., § 25 Rz. 16); in Basel-Stadt finden im summarischen Verfahren grundsätzlich weder Zeugeneinvernahmen noch Durchführungen von Expertisen statt (STAEHELIN/SUTTER, a.a.O., § 17 Rz. 2). Die Einwände der Tilgung und der Stundung der Forderung sind nach STAEHELIN/SUTTER (a.a.O., § 25 Rz. 16) vom Vollstreckungsgegner durch Urkunden zu belegen. Darauf hat sich das Appellationsgericht abgestützt und festgehalten, dass "Zeugen oder Auskunftspersonen in diesem Summarverfahren ausscheiden".
3.2 Die Beschwerdeführerin macht eine Verletzung von <ref-law> geltend. Die Vorinstanz verstosse durch die von ihr vorgenommene Beschränkung der zulässigen Beweismittel (auf Urkunden) gegen die Mindestvorschriften des Bundesrechts.
3.2.1 Nach <ref-law> muss mindestens eine Vorinstanz den Sachverhalt frei, d.h. ohne Beschränkung auf eine Willkürprüfung und ohne Bindung an prozessuale Beweisregeln überprüfen können. Es handelt sich um eine Mindestvorschrift bis zur Regelung der betreffenden Fragen durch die bundesrechtliche Prozessordnung. Nach der Schweizerischen Zivilprozessordnung vom 19. Dezember 2008 (ZPO) wird das Gericht über die Realvollstreckung im summarischen Verfahren (<ref-law>) entscheiden, in welchem der Beweis grundsätzlich durch Urkunden zu erbringen ist und andere Beweismittel nur unter gewissen Voraussetzungen zulässig sind (<ref-law>). Die materiellen Einwände der Tilgung und Stundung werden gemäss <ref-law> durch Urkunden zu beweisen sein.
3.2.2 Vorliegend hat das Appellationsgericht Zeugen und Auskunftspersonen im summarisch ausgestalteten Vollstreckungsverfahren nicht zugelassen. In anderen Kantonen - wie im Kanton Bern - ist für die Realvollstreckung ebenfalls das summarische Verfahren massgebend (<ref-law>/BE); hingegen ist festgelegt, dass der Untergang des Anspruchs (durch Erfüllung oder eingetretene Unmöglichkeit) nicht nur durch Urkunden, sondern auch durch Parteiverhör sowie andere Beweismittel wie Augenschein und Expertise bewiesen werden kann (<ref-law>/BE; LEUCH/KELLERHALS/STERCHI, Die Zivilprozessordnung für den Kanton Bern, 5. Aufl. 2000, N. 2 zu <ref-law>/BE). Ob die Auffassung des Appellationsgerichts Basel-Stadt mit den Mindestanforderungen von <ref-law> (und mit <ref-law>) vereinbar ist, braucht allerdings nicht weiter erörtert zu werden. Auch die - vom Appellationsgericht verneinte - Frage, ob im Vollstreckungsverfahren gestützt auf den Gehörsanspruch grundsätzlich das Recht besteht, die Einvernahme von Zeugen zu verlangen, ist nicht weiter auszuführen (dazu Kofmel Ehrenzeller, Die Realvollstreckung in Zivilsachen: aktuelle Fragen und Ausblick, ZZZ 2004 S. 220). Das Appellationsgericht hat erwogen, dass von der Befragung von F._ und G._ ohnehin keine Entscheidungshilfe zu erwarten sei. Was die Beschwerdeführerin gegen diese Eventualerwägung vorbringt, vermag - wie sich aus dem Folgenden ergibt - keine Rechtsverletzung darzutun.
3.3 Im Allgemeinen können in der Realexekution nur solche Einreden erhoben werden, die sich aus dem Urteil ergeben, auf Grund dessen die Vollstreckung verlangt wird, und die seit Erlass des Urteils entstanden sind. Einreden gestützt auf Tatsachen, die sich vor der Urteilsfällung ergeben haben, sind hingegen ausgeschlossen. Dies geht aus <ref-law>/BS hervor und ist in der Realvollstreckung allgemein anerkannt (vgl. Guldener, Schweizerisches Zivilprozessrecht, 3. Aufl. 1979, S. 624; Siegrist, Probleme aus dem Gebiet der Realexekution, 1958, S. 43; PFENNINGER, Die Realexekution im schweizerischen Recht, 1924, S. 57; vgl. ebenso <ref-law>; Botschaft vom 28. Juni 2006 zur Schweizerischen Zivilprozessordnung, BBl 2006 7384 Ziff. 5.24.1).
3.3.1 Die Beschwerdeführerin macht geltend, die Anhörung von F._ und G._ sei entscheidend und geboten gewesen. Sie beruft sich im Wesentlichen auf die Erwägung der Vorinstanz, wonach "von entscheidender Bedeutung" sei, ob H._ oder allfällige andere Dritte die weiteren Dispositionen als Bevollmächtigte der Eheleute A._/B._ und in deren Auftrag getätigt hätten oder ob sie unabhängig von diesen, nach eigenem System, gewirtschaftet hätten. Nach den Ausführungen der Vorinstanz trägt die Beschwerdeführerin die Beweislast für die Behauptung, der Auftrag zwischen ihr und den Ehegatten A._/B._ als Bankkunden habe sich in der Überweisung bzw. Auszahlung an H._ erschöpft; auch den Ehegatten A._/B._ sei darüber kein Auskunftsanspruch zugestanden. Mit der blossen Behauptung des insbesondere über H._ betriebenen Geldwechselsystems sei der Beschwerdeführerin - in Anbetracht der im Urteil vom 26. März 2004 festgesetzten Auskunftspflicht - jedoch ein entsprechender Beweis im "vorliegenden Vollstreckungsverfahren" nicht gelungen, weshalb eine die Endbegünstigenden umfassende Informationspflicht weiter bestehe.
3.3.2 Die Ausführungen der Beschwerdeführerin über die Rolle des Mittelmannes H._ beziehen sich nicht auf Umstände, mit welchen dargetan werden soll, dass seit Erlass des Urteils die Verbindlichkeit erfüllt sei. Ihre Vorbringen mögen zur Festlegung des Umfangs der Auskunftspflicht erheblich gewesen sein. Über die Auskunftspflicht der Beschwerdeführerin wurde allerdings rechtskräftig und verbindlich entschieden, worauf das Appellationsgericht zu Recht hingewiesen hat. Das Vollstreckungsgericht ist an das zu vollziehende Urteil gebunden (vgl. <ref-ruling> E. 2 S. 373; Urteil 5A_627/2007 vom 28. Februar 2008 E. 3.1). Zu Recht weist daher die Beschwerdegegnerin darauf hin, dass die Nennung von H._ als diejenige Person, welche angeblich über die Konten der Ehegatten A._/B._ verfügt habe und über welchen Überweisungen erfolgt seien, noch keine Erfüllung des Sachurteils bedeute. Denn das Urteil vom 26. März 2004 sieht unmissverständlich die Pflicht zum vollständigen Aufschluss durch bankübliche Belege unter namentlicher Angabe sämtlicher Empfänger, insbesondere der Transaktionen gemäss Liste vom 6. Februar 1990 vor. Wenn die Beschwerdeführerin sich auf den Standpunkt stellt, sie sei im Hauptprozess insoweit nicht verpflichtet gewesen, die Erfüllung der Auskunftspflicht zu thematisieren, sondern erst im Vollstreckungsverfahren, macht sie selber deutlich, dass sich ihre Einwände gegen den Umfang der aus dem Urteil vom 26. März 2004 ergehenden Leistungspflicht richten. Dafür bestand indessen im ursprünglichen Verfahren, das zur Auskunftspflicht führte, Gelegenheit. Vor diesem Hintergrund ist nicht zu beanstanden, wenn das Appellationsgericht im angefochtenen Entscheid im Ergebnis angenommen hat, die Anhörung von F._ und G._ sei für den Nachweis der seit Erlass des Urteils eingetretenen Erfüllung nicht erheblich und dieses Beweismittel im Vollstreckungsverfahren nicht abzunehmen. Insoweit ist der Vorwurf der Beschwerdeführerin, die Vorinstanz habe ihren Anspruch auf rechtliches Gehör bzw. den Beweis verletzt oder sei in Anwendung kantonalen Rechts in Willkür oder überspitzten Formalismus verfallen, unbegründet.
3.3.3 Die Beschwerdeführerin wirft der Vorinstanz weiter Willkür vor, weil sie die von der Beschwerdegegnerin in das Verfahren eingebrachten Listen über Auszahlungen einseitig gewürdigt und angenommen habe, die Listen wären bereits im Hauptverfahren zu thematisieren gewesen. Das Appellationsgericht hat in diesem Zusammenhang ausdrücklich erwogen, dass die Beschwerdeführerin aus einer der Listen nicht erst im Vollstreckungsverfahren die hinreichende Erfüllung der Auskunftspflicht ableiten könne. Was die Beschwerdeführerin gegen die Auskunftspflicht im Prozess nicht eingewendet habe, könne sie unter Berufung auf die betreffende Liste im Vollstreckungsverfahren nicht nachholen. Die Beschwerdeführerin übergeht in ihren Ausführungen, dass es im Vollstreckungsverfahren nicht um den Auskunftsanspruch der Beschwerdegegnerin, sondern einzig um die Vollstreckbarkeit des Urteils aus dem Jahre 2004 geht. Sie legt nicht dar, inwiefern die Auffassung der Vorinstanz, dass es bei ihren Einwendungen um Tatsachen geht, die sich vor Urteilsfällung ereignet haben und im Vollstreckungsverfahren ausgeschlossen sind, willkürlich sein soll. Sodann hat das Appellationsgericht festgehalten, die zweite Liste mit dem Vermerk, wonach A._ die der Bank belasteten Beträge in K._ in bar erhalten habe, bestätige allenfalls, dass die Bank das Geld nicht selber widerrechtlich verwendet habe. Hingegen werde damit der Auskunftsanspruch der Beschwerdegegnerin, welche gemäss Urteil vom 26. März 2004 zum vollständigen Anspruch auf Information wie auf Kontoauszüge, Zahlungseingänge, Gutschriftenanzeigen etc. verpflichte, nicht ausgeschlossen bzw. sei dieser weiterhin nicht erfüllt. Inwiefern die Anwendung des kantonalen Vollstreckungsrechts geradezu unhaltbar (vgl. zum Willkürbegriff: <ref-ruling> E. 3.1 S. 473) sein soll, setzt die Beschwerdeführerin nicht auseinander. Insoweit genügt die Beschwerde den Begründungsanforderungen nicht (<ref-law>).
3.4 In der Realexekution kann nach der Lehre der Vollstreckungsgegner die Abweisung eines Vollstreckungsbegehrens verlangen mit der Begründung, die Erfüllung des Anspruchs sei objektiv unmöglich (Siegrist, a.a.O., S. 44), weil z.B. eine herauszugebende Sache nach Erlass des zu vollstreckenden Urteils zerstört wurde (vgl. BULACHER, Die Realexekution nach den Zivilprozessordnungen der Kantone Basel-Stadt und Basel-Landschaft, 1988, S. 75 f.). Vorliegend macht die Beschwerdeführerin nicht geltend, dass das Appellationsgericht eine objektive Unmöglichkeit der Realexekution übergangen habe. Sie betont selber vielmehr, dass mit den bereits ausgehändigten Unterlagen die Auskunftspflicht erfüllt sei und weitergehende Fragen der Beschwerdeführerin von der Auskunftspflicht gemäss Urteil vom 26. März 2004 nicht erfasst seien. Insoweit ist das Urteil des Appellationsgerichts über die Vollstreckung nicht zu beanstanden.
3.5 Im Übrigen kann von einer Verletzung von <ref-law> bzw. des Anspruchs auf eine Entscheidbegründung keine Rede sein kann (<ref-ruling> E. 2b S. 102; <ref-ruling> E. 4.3 S. 540), da im angefochtenen Entscheid betreffend Zulässigkeit des Fragenkatalogs die Überlegungen genannt werden, von denen sich das Appellationsgericht leiten liess und auf welche es sich stützt. Dass die angerufenen Normen der EMRK und kantonalen verfassungsmässigen Rechte weitergehenden Schutz als die Bundesverfassung bieten würden, behauptet die Beschwerdeführerin nicht, so dass sich Erörterungen über eine allfällige Verletzung erübrigen.
3.6 Nach dem Dargelegten vermag die Beschwerdeführerin mit ihren Rügen nicht durchzudringen. Der Entscheid des Appellationsgerichts, mit welchem die Einwände der Beschwerdeführerin gegen die Vollstreckung des Urteils vom 26. März 2004 verworfen wurden, hält vor Bundes- und Völkerrecht sowie kantonalen verfassungsmässigen Rechten stand.
4. Aus diesen Gründen ist die Beschwerde in Zivilsachen abzuweisen, soweit darauf überhaupt eingetreten werden kann. Bei diesem Ausgang des Verfahrens wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1, Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Eingabe wird als Beschwerde in Zivilsachen entgegengenommen.
2. Die Beschwerde in Zivilsachen wird abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von Fr. 5'000.-- werden der Beschwerdeführerin auferlegt.
4. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 5'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 5. Mai 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Levante