Sachverhalt:
A. A._ und B._ waren französische Staatsangehörige und wohnten in Frankreich. Sie heirateten in den 1930er Jahren 1933, ohne je einen Ehevertrag abzuschliessen. B._ verstarb im Jahre 1987 und A._ im Jahre 2002. Ihre einzige Tochter Z._ ist testamentarische und gesetzliche Alleinerbin. Sie hatte bereits im Jahre 1990 bei der X._ AG schriftlich den Antrag auf Auskunft über die für ihre Eltern bzw. ihren Vater verwalteten Vermögenswerte gestellt. Dieses und weitere Auskunftsgesuche blieben erfolglos. Am 20. Oktober 2003 erhob Z._ Klage beim Zivilgericht Basel-Stadt gegen die X._ AG und stellte verschiedene Auskunftsbegehren. Das Zivilgericht hiess die Klage mit Urteil vom 14. Dezember 2006 vollumfänglich gut und verpflichtete die X._, Z._ in folgender Weise Auskunft zu erteilen:
"1. Die Beklagte wird unter Androhung der Ungehorsamstrafe gegen ihre verantwortlichen Organe nach <ref-law> im Widerhandlungsfall (Busse bis CHF 10'000.--) verurteilt, der Klägerin schriftlich und unter Vorlage aller Beweisdokumente oder anderweitiger Aufzeichnungen (z.B. Tonbänder), die sie besitzt oder beschaffen kann, vollständigen Aufschluss zu erteilen über alle bei der Beklagten hinterlegten oder von ihr verwalteten beweglichen oder unbeweglichen Vermögenswerte wie Wertschriften- und Edelmetalldepots, Guthaben, Schrankfächer und alle anderen Vermögenswerte irgendwelcher Art,
- welche, sei es einzeln oder gemeinsam, sei es in eigenem Namen, sei es unter Verwendung eines Decknamens oder von Nummern, von Me A._ und/ oder seiner Ehefrau B._ hinterlegt bzw. errichtet wurden;
- oder welche von der Beklagten oder sonstigen Dritten, wie zum Beispiel Gesellschaften, Notaren, Trusts, Stiftungen, Anstalten etc. treuhänderisch für Rechnung von Me A._ und/oder Frau B._ gehalten werden;
- oder die im Eigentum Dritter gestanden haben, deren wirtschaftliche Benefiziare aber Me A._ und/oder Frau B._ gewesen sind,
a) für Stichtag xxxx 1987,
b) für Stichtag yyyy 2002,
c) für den Zeitraum vor dem xxxx 1987 betreffend die obgenannten Vermögenswerte, deren Entwicklung, 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, ebenso über die Öffnungen von eventuellen Schrankfächern; dabei ist anzugeben, woher die betreffenden Zuflüsse gekommen und wohin die betreffenden Abflüsse gegangen sind;
d) für den Zeitraum nach dem xxxx 1987 bis zum heutigen Tag betreffend die obgenannten Vermögenswerte, deren Entwicklung, insbesondere was Erträgnisse, andere Vermögenszuflüsse und Vermögensabflüsse irgendwelcher Art betrifft, auch wenn die entsprechenden Depots, Konti usw. am heutigen Tag nicht mehr bestehen sollten, ebenso über die Öffnungen von eventuellen Schrankfächern; dabei ist anzugeben, woher die betreffenden Zuflüsse gekommen und wohin betreffende Abflüsse gegangen sind;
2. Insbesondere wird die Beklagte zur Herausgabe von Kopien der folgenden Unterlagen verpflichtet:
- alle Quittungen mit den entsprechenden notwendigen Unterschriften,
- alle Weisungen, Genehmigungen von Rechnungsabschlüssen und Entlassungserklärungen mit den entsprechenden ordnungsgemäss beigesetzten Unterschriften,
- alle von der Beklagten erstellten Notizen über telefonisch erteilte Weisungen,
- alle übrigen Dokumente, welche die X._ bzw. allenfalls die Y._ als Rechtsnachfolgerin und/oder Me A._ geschrieben und/oder signiert haben,
- alle Korrespondenzen, welche auf die verwalteten Aktiven Bezug nehmen,
- alle internen Notizen; welche darauf Bezug nehmen,
- alle Instruktionen und Verfügungen auf den Todesfall von Me A._ und/ oder Frau B._,
alles für die Jahre mindestens ab 1978."
B. Die X._ erhob gegen das Urteil des Zivilgerichts Appellation und verlangte die Abweisung der Auskunftsklage. Mit Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 17. Juni 2009 wurde die Appellation abgewiesen und das erstinstanzliche Urteil bestätigt.
C. Mit Eingabe vom 18. September 2009 führt die X._ Beschwerde in Zivilsachen. Die Beschwerdeführerin beantragt dem Bundesgericht, das Urteil des Appellationsgerichts aufzuheben und die Klage abzuweisen. Eventualiter verlangt sie, die Sache zu neuer Entscheidung an das Appellationsgericht zurückzuweisen. Subeventualiter sei das Urteil des Appellationsgerichts insoweit aufzuheben, als sie verpflichtet werde, auch über Kontos Dritter Auskunft zu erteilen, und die Klage sei insoweit abzuweisen, als Auskünfte und die Edition von Belegen betreffend Kontobeziehungen mit Drittkunden (der Beschwerdeführerin) gefordert werden. Weiter verlangt die Beschwerdeführerin aufschiebende Wirkung.
Mit Präsidialverfügung vom 9. Oktober 2009 wurde der Beschwerde aufschiebende Wirkung zuerkannt.
Z._ als Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei; eventuell sei die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Das Appellationsgericht beantragt die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Das angefochtene 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. 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 die gesetzliche Streitwertgrenze von Fr. 30'000.-- erreicht (<ref-law>). 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) und die Beschwerdeführerin ist zur Beschwerdeerhebung befugt (<ref-law>). Der angefochtene Entscheid schliesst das Verfahren ab (<ref-law>). Die Beschwerde in Zivilsachen ist grundsätzlich zulässig.
1.2 Beim angefochtenen Entscheid über die Auskunftspflicht 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>), und es kann die Verletzung von u.a. Bundesrecht (<ref-law>; Urteil 4A_15/2009 vom 15. September 2009 E. 1.3, nicht publ. in: <ref-ruling>) und im Rahmen von <ref-law> die Anwendung von ausländischem Recht gerügt werden. Die Verletzung kantonaler Gesetze kann das Bundesgericht nur insoweit prüfen, als in der Beschwerde entsprechende Verfassungsrügen erhoben werden (vgl. <ref-law>).
1.3 In der Beschwerdebegründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>); blosse Verweise auf die Akten und andere Rechtsschriften sind unzulässig (vgl. <ref-ruling> E. 1d). 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). Das Bundesgericht ist an den vorinstanzlich festgestellten Sachverhalt gebunden (<ref-law>). Zulässig ist einzig die Rüge, dass eine Tatsachenfeststellung auf einer Rechtsverletzung im Sinne von <ref-law> beruhe oder eine Tatsache offensichtlich unrichtig festgestellt worden sei (<ref-law>), wobei "offensichtlich unrichtig" mit "willkürlich" gleichzusetzen ist (<ref-ruling> E. 7.1 S. 398 mit Hinweisen).
2. Das Appellationsgericht hat vorab festgehalten, dass die Noveneingabe der Beschwerdeführerin vom 12. Juni 2009 sowie die anlässlich der Hauptverhandlung eingereichten Dokumenten verspätet seien und daher gemäss § 237 Abs. 2 und 3 ZPO/BS nicht berücksichtigt werden könnten. Zudem wäre eine Berücksichtigung nicht entscheidend, da ein Rückgriff auf das nach französischem Recht zu beurteilende gesetzliche (erbrechtliche) Auskunftsrecht nicht nötig sei, weil die Klage bereits gestützt auf das vertragliche (auftragsrechtliche) Auskunftsrecht, auf welches schweizerisches Recht anwendbar sei und welches die Beschwerdegegnerin erbrechtlich von ihrem Vater erworben habe, gutzuheissen sei. Das Auftragsverhältnis zwischen der Beschwerdeführerin und A._ sowie der Informationsanspruch gemäss <ref-law> seien unbestritten, ebenso wenig der Übergang dieses Anspruchs auf die Beschwerdegegnerin und die Verjährungsfrist von 10 Jahren.
2.1 Das Appellationsgericht hat zunächst den Einwand der Beschwerdeführerin geprüft, wonach der Auskunftsanspruch der Beschwerdegegnerin bereits im Jahre 1997 verjährt sei, weil die auftragsrechtliche Beziehung zwischen ihr und A._ mit der Kontosaldierung im November 1987 beendet worden sei. Die Vorinstanz hat erwogen, dass die Einrede der Verjährung nicht in hinreichend substantiierter Weise erhoben worden sei. Im Übrigen sei der Auskunftsanspruch nicht verjährt, weil konkrete Anhaltspunkte (verschiedene Schreiben, Aussage des Zeugen C._) dafür vorlägen, dass die vertragliche Beziehung zwischen der Beschwerdeführerin und A._ über das Jahr 1987 weiterbestanden habe und am 20. Oktober 1993 noch nicht beendet gewesen sei. Welcher Art die Kontobeziehung zwischen der Beschwerdeführerin und A._ gewesen sei, spiele keine Rolle. Anhaltspunkte dafür, dass der seinerzeitige Bankvertrag im Jahre 1987 aufgelöst worden sei, d.h. die späteren Überweisungen bzw. Auszahlungen nicht im Rahmen einer bestehenden Bankbeziehung erfolgt seien, würden nicht bestehen. Selbst ausserhalb einer Bankverbindung mit der Beschwerdeführerin bestehe wohl für Einzahlungen bzw. für die Beträge, welche A._ zugeflossen worden seien, eine Auskunftspflicht zugunsten der Beschwerdegegnerin als Erbin.
2.2 Sodann sei der Anspruch auf Auskunft nicht unmöglich bzw. verwirkt, da die Beschwerdeführerin selber einzig von der Vernichtung des Kundendossiers durch A._ spreche, und weitere bankeigene Akten noch vorhanden seien, zumal auch der Zeuge C._ von weiteren Akten gesprochen habe. Anhaltspunkte für die Annahmen, dass A._ mit der Aktenvernichtung das Auskunftsrecht seiner Tochter ausschliessen habe wollen, würden nicht bestehen. Sodann könne die Beschwerdeführerin der Beschwerdegegnerin (als Rechtsnachfolgerin) nicht entgegenhalten, A._ bereits informiert zu haben bzw. dieser habe kein Interesse an der Information gehabt. Die Beschwerdegegnerin habe den auftragsrechtlichen Anspruch auf Rechenschaftsablegung von ihrem Vater geerbt, weshalb von fehlendem schützenswerten Interesse oder Rechtsmissbrauch nicht gesprochen werden könne. Entgegen der Auffassung der Beschwerdeführerin verlange die Beschwerdegegnerin keine Auskunft über Drittkonti, sondern würden Dritte nur interessieren, soweit diese durch bzw. über die Beschwerdeführerin abgewickelte Geschäfte bzw. Zahlungen zu ihrem Vater in Beziehung gestanden hätten.
3. Die Beschwerdeführerin wirft dem Appellationsgericht eine Reihe fehlerhafter Sachverhaltsfeststellungen vor. Sie macht weiter im Wesentlichen geltend, dass die Nichtberücksichtigung der Noven, die Annahme der Nichtverjährung des Informationsanspruchs sowie u.a. die Ausdehnung der Auskunftspflicht auf Konti Dritter gegen Bundesrecht verstosse.
3.1 Zunächst rügt die Beschwerdeführerin als fehlerhafte Feststellung im Sachverhalt, dass sie von der Vorinstanz an verschiedener Stelle als "Bank" bezeichnet werde und von den Rechtsbeziehungen zu A._ als "Bankvertrag" bzw. "Bankbeziehung" die Rede sei, währenddem sie lediglich Vermögensverwalterin sei, ohne dem Bankengesetz unterstellt zu sein. Die Beschwerdeführerin legt nicht dar, inwiefern die von der Vorinstanz verwendeten Begriffe in tatsächlicher Hinsicht für den Ausgang des Verfahrens entscheidend sind (vgl. <ref-law>). Dass sie - wie eine Bank - auftragsrechtliche Beziehungen zu A._ unterhielt und dieser ein "Konto" hatte, ist unbestritten. Insoweit geht die Sachverhaltsrüge ins Leere. Dass die Vorinstanz bankenspezifische Bestimmungen angewendet habe, welche für die Bestätigung des Auskunftsanspruchs erheblich gewesen seien, macht sie übrigens zu Recht nicht geltend.
3.2 Weiter kritisiert die Beschwerdeführerin, dass die Vorinstanz (in Erwägung Ziff. 1.1) gestützt auf das Schreiben vom 18. Mai 1993 betreffend Höhe des Streitwerts festgehalten habe, "im Zeitraum 1987 bis 1993 [seien] Summen in Höhe von USD 541'500 auf das Konto von A._ eingegangen". Aus ihrem Schreiben gehe nicht hervor, dass die Gelder auf ein Konto von A._ eingegangen seien. Die Vorinstanz bezieht sich allerdings auf die Höhe des Streitwertes, welcher die Streitwertgrenze von <ref-law>/BS (Fr. 8'000.--) offensichtlich übersteige. Andere Schlüsse hat die Vorinstanz insoweit nicht gezogen, zumal die Beschwerdeführerin weder Streitwert noch Streitwertberechnung für das kantonale Rechtsmittel in Frage stellt. Die Beschwerdeführerin übergeht, dass die für den Verfahrensausgang entscheidenden Tatsachenfeststellungen zur Dauer der vertraglichen Beziehungen an anderer Stelle getroffen wurden. Insoweit sind die Ausführungen der Beschwerdeführerin, wonach der vorinstanzliche Sachverhalt unrichtig festgestellt worden sei, unbehelflich.
3.3 Die Beschwerdeführerin wirft sodann der Vorinstanz vor, ihre mit der Noveneingabe vom 12. Juni 2009 und ihre an der Hauptverhandlung (vom 17. Juni 2009) vorgelegten Unterlagen in verfassungswidriger Weise nicht berücksichtigt zu haben.
3.3.1 Im Appellationsverfahren nach der ZPO/BS gilt, dass Noven, welche der betreffenden Partei erst nach Aktenschluss zur Kenntnis kommen, "baldmöglichst und spätestens am dritten Tag vor dem Verhandlungstag" einzugeben sind (<ref-law>/BS; STAEHELIN/ SUTTER, Zivilprozessrecht nach den Gesetzen der Kantone Basel-Stadt und Basel-Landschaft unter Einbezug des Bundesrechts, 1992, § 21 Rz. 48). Soweit die Beschwerdeführerin insbesondere Willkür geltend macht, weil das Appellationsgericht nicht auf das gesetzliche Kriterium der Kenntnisnahme, sondern auf den "Zeitpunkt des frühestmöglichen Anlasses für die Novensuche" abgestellt habe, ist ihr Vorbringen unbehelflich. Mit der gesetzlichen Bestimmung wird nicht bloss der spätest mögliche Zeitpunkt, sondern zusätzlich die "baldmöglichste" Noveneingabe vorgeschrieben. Auch in der Lehre ist für das Novenrecht anerkannt, dass im Verfahren vor dem Appellationsgericht neue Tatsachen im frühest möglichen Zeitpunkt geltend gemacht werden müssen, um für das Urteil Berücksichtigung zu finden (STAEHELIN/SUTTER, a.a.O.).
3.3.2 Das Appellationsgericht hat die am 12. Juni 2009 bzw. der Hauptverhandlung vorgelegten Noven gestützt auf <ref-law>/BS als unzulässig erklärt, weil sie nicht "baldmöglichst" eingereicht worden seien. Das Parteigutachten der Gegenseite genüge nicht als Anlass, weil die Appellationsantwort bereits vom 17. Dezember 2008 datiere und das Urteil der Cour d'Appel de D._ vom 30. Juni 1992, welches Hauptgrund der Noveneingabe gewesen sein soll, ebenfalls (als Klagebegründungsbeilage) bereits lange bekannt gewesen sei. Auch das mit der Noveneingabe eingereichte Schreiben von E._ vom 9. Juni 2009 sei kein echtes und damit zulässiges Novum, weil die betreffende Bestätigung bereits mit dem (der Klageantwort beigelegten) Schreiben der E._ vom 15. April 2004 hätte erfolgen können. Insoweit ist nicht ersichtlich, dass das Appellationsgericht das kantonale Recht überspitzt formalistisch bzw. in geradezu unhaltbarer Weise (<ref-law>; zum Willkürbegriff: <ref-ruling> E. 3.1 S. 473) angewendet haben sollte.
3.3.3 Die Beschwerdeführerin beruft sich sodann auf die Verfügung des Appellationsgerichts vom 23. Dezember 2008, mit welcher die Appellationsantwort (der Beschwerdegegnerin) zur Kenntnisnahme mitgeteilt sowie der Schluss des Schriftenwechsels verfügt wurde. Aus dem Hinweis "weitere Instruktionsverfügungen werden folgen" kann die Beschwerdeführerin hingegen nicht ableiten, das Appellationsgericht werde sich von Amtes wegen über die Zulässigkeit von neuen Behauptungen und Beweismittel in der Appellationsantwort aussprechen. Sie hält selber fest (und nichts anderes geht aus der von ihr angeführten kantonalen Rechtsprechung hervor), dass zur Geltendmachung von Noven eine Eingabe der betreffenden Partei erforderlich ist. Von einer Verletzung ihres Anspruchs, nach Treu und Glauben behandelt zu werden (<ref-law>), kann keine Rede sein. Die Beschwerdeführerin legt in diesem Zusammenhang nicht hinreichend dar (<ref-law>), inwiefern sie - als Gesuchstellerin - sich vor Erlass des belastenden Entscheides (Nichtberücksichtigung der Noveneingabe) nicht zur Sache habe äussern können und deshalb ihr Gehörsanspruch verletzt (<ref-law>; <ref-ruling> E. 2b S. 56) bzw. ihr Anspruch auf eine Entscheidbegründung oder das Verhältnismässigkeitsprinzip (<ref-law>) verletzt worden sei.
3.3.4 Die Beschwerdeführerin wendet weiter ein, die Ausführungen der Beschwerdegegnerin in der Appellationsantwort betreffend die Bezahlung der Rechnung F._ hätten zur Noveneingabe veranlasst. Sie legt allerdings nicht dar, inwiefern das Appellationsgericht in willkürlicher Weise angenommen habe, die Noven seien nicht "baldmöglichst" eingereicht worden. Der Hinweis auf die F._-Rechnung in der Appellationsantwort vermag nicht darzutun, inwiefern die Auffassung der Vorinstanz, der Inhalt des Schreibens der E._ vom 9. Juni 2009 hätte bereits mit demjenigen vom 15. April 2004 mitgeteilt werden können, geradezu unhaltbar sei. Aus diesem Grund kann von willkürlicher Anwendung des kantonalen Novenrechts nicht gesprochen werden, wenn die Vorinstanz angenommen hat, mit dem Schreiben der E._ vom 9. Juni 2009 würden lediglich die Angaben des (mit der Klageantwort eingereichten) Schreibens der E._ vom 15. April 2004 verbessert, weshalb es (als unechtes Novum) nicht berücksichtigt werden könne. Weiter macht die Beschwerdeführerin vergeblich geltend, die Vorinstanz habe gestützt auf ihre Noveneingabe vom 12. Juni 2009 aktenwidrige bzw. unrichtige Feststellungen getroffen, was den Inhalt des Schreibens von E._ vom 9. Juni 2009 einschliesslich der Kurzbezeichnung "G._" in Unterlagen zum Trustkonto mit Bezug auf die wirtschaftliche Berechtigung Dritter betreffe. Diese Ausführungen gehen ins Leere, weil das Appellationsgericht die betreffende Noveneingabe - wie dargelegt ohne die Verfassung zu verletzen - ausser Acht lassen durfte.
3.3.5 Die Beschwerdeführerin stellt nicht in Frage, dass auf die vertragliche Beziehung zwischen ihr und A._ bzw. der Beschwerdegegnerin als dessen Rechtsnachfolgerin schweizerisches Recht (vgl. <ref-law>) anwendbar sei. Ihre Erörterungen zum französischen Erbrecht gehen insoweit an der Sache vorbei. Zum einen übergeht sie, dass laut Vorinstanz das - ebenfalls in der Sache der Beschwerdegegnerin ergangene - Urteil der Cour d'Appel de D._ vom 30. Juni 1992 der Klagebegründung beigelegen hat und aus diesem Grund kein Novum ist. Inwiefern diese Auffassung willkürlich sei, legt die Beschwerdeführerin nicht hinreichend dar (<ref-law>). Zum anderen hält sie selber fest, dass nach schweizerischen Vertragsstatut (vgl. <ref-law>) kein besonderer Interessennachweis notwendig sei, sondern die Pflicht zur Rechenschaftsablegung bzw. Auskunftserteilung zur Leistungspflicht des Beauftragten gehört (vgl. Fellmann, Berner Kommentar, N. 56 zu Art. 400). Wohl kann nach der Lehre die Pflicht zur Auskunftserteilung mangels Rechtsschutzbedürfnis des Auftraggebers verneint werden, wenn zum vornherein feststeht oder mit an Sicherheit grenzender Wahrscheinlichkeit anzunehmen ist, dass der Berechtigte trotz der erfolgten Rechenschaftsablegung vom Verpflichteten nichts zu fordern hat (FELLMANN, a.a.O., N. 84 zu Art. 400). Inwiefern diese Voraussetzungen erfüllt seien bzw. ein auftragsrechtlicher Auskunftsanspruch fehlen soll, vermag die Beschwerdeführerin mit ihrem Hinweis, dass nach französischem Erbrecht ein Auskunftsinteresse fehle, nicht darzutun.
3.3.6 Nach dem Dargelegten verstösst nicht gegen die Verfassung, wenn die Vorinstanz die von der Beschwerdeführerin eingereichten Noven nicht berücksichtigt hat.
3.4 Die Beschwerdeführerin macht im Wesentlichen geltend, die Annahme der Vorinstanz, dass die vertragliche Beziehung zwischen der Beschwerdeführerin und A._ über das Jahr 1987 weiterbestanden habe und am 20. Oktober 1993 noch nicht beendet gewesen sei, beruhe auf bundesrechtswidrigen Sachverhaltsfeststellungen und Beweiswürdigungen. Vielmehr habe seit 1988 keine Konto- bzw. Kundenbeziehung zu A._ bestanden, weshalb die Auskunftsklage infolge Verjährung abzuweisen sei.
3.4.1 Das Appellationsgericht hat verschiedene Schreiben der Beschwerdeführerin gewürdigt. Darin sei insbesondere die Feststellung enthalten, dass mit A._ seit vielen Jahren Beziehungen unterhalten würden (Schreiben vom 10. Mai 1990; "que nous entretenons depuis des années ... des rapports"), auch "nach 1993" noch Zahlungen als Spesenersatz ausgerichtet worden seien (Schreiben vom 20. Mai 2003) und A._ zwischen 1987 und 1993 eine Anzahl namhafter Beträge zugeflossen seien (Schreiben vom 18. Mai 1993) und von der Rücksprache "mit unserem Kunden" die Rede sei (Schreiben vom 15. Dezember 1997). Sodann habe der Zeuge C._ (als Mitarbeiter der Beschwerdeführerin) erklärt, dass die Beschwerdeführerin A._ auch nach 1987 mehrmals Gelder, teilweise in bar ausbezahlt habe. Die wiederholte Auszahlung von grossen Summen in bar an dieselbe in Person durch die Beschwerdeführerin als Treuhandgesellschaft erlaube - wie die Erstinstanz bereits festgehalten habe - die Annahme einer Kundenbeziehung. Gestützt auf die konkreten Anhaltspunkte hat die Vorinstanz geschlossen, dass die vertragliche Beziehung zwischen der Beschwerdeführerin und A._ über das Jahr 1987 weiterbestanden habe und am 20. Oktober 1993 noch nicht beendet gewesen sei.
3.4.2 Das Appellationsgericht hat vorliegend nicht einfach auf die Vorbringen der Beschwerdegegnerin ohne Beweiserhebung abgestellt, sondern sich vielmehr auf Grund von Urkunden und Zeugenaussagen über den Sachverhalt eine eigene Meinung gebildet und damit für das Bundesgericht nach <ref-law> verbindliche Feststellungen getroffen. Soweit die Beschwerdeführerin eine Verletzung der Regeln über die Beweislast (<ref-law>) bzw. Folgen der Beweislosigkeit rügt, gehen ihre Ausführungen daher ins Leere (vgl. <ref-ruling> E. 2 S. 291).
3.4.3 Die Beschwerdeführerin führt aus, dass im Schreiben vom 10. April 1990 zwar von "rapports" die Rede sei, darunter jedoch keine vertragliche, sondern nur "geschäftliche Beziehungen im weiteren Sinne" belegt seien. Aus dem Schreiben vom 20. Mai 2003 und der von ihr bestätigten Ausrichtung von "Zahlungen ... als Spesenersatz" könne keine Vertragsbeziehung zu A._, sondern zu Dritten abgeleitet werden. Auch im Schreiben vom 18. Mai 1993 werde lediglich der Zufluss von Geldbeträgen ("sommes attribuées") von der Beschwerdeführerin zu A._ bestätigt, nicht aber eine vertragliche Beziehung. Im Schreiben vom 15. Dezember 1997 habe sie lediglich aus Versehen von "unserem Kunden", und nicht von "unserem ehemaligen Kunden" gesprochen. Die Vorinstanz habe ihre Auskünfte wie im Schreiben vom 28. Januar 1999, wonach die Kundenbeziehung vor über 10 Jahren aufgelöst worden sei, unrichtig gewichtet. Die Beschwerdeführerin übergeht mit diesen Ausführungen allerdings, dass die Vorinstanz unter Berücksichtigung der verschiedenen Beweismittel in tatsächlicher Hinsicht lediglich andere als die von ihr dargelegten Schlüsse gezogen hat. Das Gleiche gilt für den Schluss der Vorinstanz, dass die vom Zeugen C._ bestätigten, zum Teil in bar erfolgten Geldauszahlungen vorliegend ein Kundenverhältnis annehmen lassen, währenddem die Beschwerdeführerin festhält, dass dieser Umstand gerade gegen den Fortbestand einer vertraglichen Beziehung spreche. Mit ihren weiteren Ausführungen will die Beschwerdeführerin sodann vergeblich den "(Gegen-)Beweis" dafür erbringen, dass es sich bei den im Schreiben vom 18. Mai 1993 aufgeführten Summen lediglich um Zahlungen ab einem Drittkonto an A._ bzw. zu dessen Gunsten gehandelt habe und für eine weitere Konto-/Kundenbeziehung zu A._ kein Raum bleibe. Willkürliche Beweiswürdigung liegt nicht schon vor, wenn vom Sachgericht gezogene Schlüsse nicht mit der Darstellung der Beschwerdeführerin übereinstimmen, sondern offensichtlich unhaltbar sind (<ref-ruling> E. 1b S. 30). Was die Beschwerdeführerin als Willkür, Aktenwidrigkeit und Verletzung des rechtlichen Gehörs bzw. Beweisführungsanspruchs rügt, stellt unzulässige appellatorische Kritik an der Beweiswürdigung dar (<ref-law>).
3.4.4 Der weitere Hinweis der Vorinstanz, dass die Beschwerdeführerin keine Unterlagen über die Kontoauflösung ins Recht gelegt habe, obwohl diese regelmässig schriftlich erfolge, ist für sich allein nicht entscheiderheblich; insoweit ist die Kritik in der Beschwerdeschrift unbehelflich. Das Vorbringen, bereits vor dem Zivilgericht seien Tatsachen (wie die Saldierung der Kontobeziehung) zu Unrecht als strittig betrachtet worden, obwohl sie bereits im erstinstanzlichen Verfahren anerkannt worden seien, ist eine Rüge in tatsächlicher Hinsicht. Dass diese - gegen das erstinstanzliche Urteil gerichtete - Rüge vor dem Appellationsgericht erhoben und zu Unrecht übergangen worden sei, macht die Beschwerdeführerin nicht geltend. Das Vorbringen ist neu und daher unzulässig. Soweit die Beschwerdeführerin schliesslich die Nichtabnahme weiterer Beweismittel bzw. die Nichtwiederholung von Zeugenbefragungen rügt, übergeht sie, dass <ref-law> dem Richter nicht vorschreibt, mit welchen Mitteln er den Sachverhalt abzuklären hat (vgl. <ref-ruling> E. 2 S. 290); sie legt insoweit nicht hinreichend dar, inwiefern eine von der Vorinstanz vorweggenommene Beweiswürdigung gegen das Willkürverbot verstossen soll.
3.4.5 Damit bleibt es bei der vorinstanzlichen Sachverhaltsfeststellung, dass die vertragliche (auftragsrechtliche) Beziehung zwischen der Beschwerdeführerin und A._ über das Jahr 1987 weiterbestanden hat und am 20. Oktober 1993 noch nicht beendet gewesen ist. Dass der Anspruch auf Rechenschaftsablegung bzw. Auskunftserteilung zehn Jahre (<ref-law>) nach Beendigung des Auftragsverhältnisses verjährt (Urteil 5C.305/2005 vom 18. April 2006 E. 2.2; WERRO, in: Commentaire Romand, Code des obligations I, 2003, N. 21 zu Art. 400; FELLMANN, a.a.O., N. 99 zu Art. 400) und vorliegend - bei am 20. Oktober 1993 noch nicht beendeter Vertragsbeziehung - die auftragsrechtliche Auskunftsklage nicht verjährt ist bzw. die Verjährungsfrist wirksam unterbrochen wurde, ist unbestritten. Insoweit ist nicht zu beanstanden, wenn das Appellationsgericht angenommen hat, die ererbten vertraglichen Informationsansprüche der Beschwerdegegnerin seien nicht verjährt. Ob die Vorinstanz zu Recht annehmen durfte, dass die Beschwerdeführerin die Einrede der Verjährung nicht in hinreichend substantiierter Weise erhoben habe, braucht bei diesem Ergebnis nicht erörtert zu werden. Das Gleiche gilt für die (in einer Eventualerwägung der Vorinstanz unter Hinweis auf <ref-ruling>) zur Verjährung aufgeworfene Frage, ob selbst ausserhalb einer Bankverbindung mit der Beschwerdeführerin für Einzahlungen bzw. für die Beträge, welche A._ zugeflossen worden seien, eine Auskunftspflicht für die Beschwerdegegnerin als Erbin zustehe.
3.5 Die Beschwerdeführerin wirft dem Appellationsgericht weiter vor, die Unmöglichkeit des Anspruchs auf Auskunft übergangen zu haben, weil die Unterlagen vernichtet worden seien und die Existenz von Unterlagen eine materielle Voraussetzung des Anspruchs sei. Nach der Lehre gehört zur Rechenschaftsablegung die Vorlage von Belegen, soweit solche vorhanden sind (FELLMANN, a.a.O., N. 28 zu Art. 400), bzw. wird der Beauftragte von der Rechenschaftsablegungspflicht befreit, wenn die abzuliefernde Sache untergegangen ist (vgl. WEBER, in: Basler Kommentar, Obligationenrecht I, 3.Aufl., N. 24 zu Art. 400; Schröder, Informationspflichten im Erbrecht, 2000, S. 30 f.). Die Vorinstanz hat festgehalten, dass der Auskunftsanspruch nicht unmöglich sei, da die Beschwerdeführerin selber einzig von der Vernichtung des Kundendossiers durch A._ spreche, und weitere bankeigene Akten noch vorhanden seien, da der Zeuge C._ von weiteren Akten gesprochen habe. Die Beschwerdeführerin übergeht, dass die im Sachverhalt festgestellte Existenz von Unterlagen einen Schluss in tatsächlicher Hinsicht darstellt. Ihre Ausführungen (u.a. zur Zeugenaussage C._), mit denen sie die unzutreffenden Vermutungen im angefochtenen Urteil widerlegen will, stellen eine unzulässige Kritik an der Beweiswürdigung bzw. am - für das Bundesgericht verbindlichen - vorinstanzlich festgestellten Sachverhalt dar und können ebenso wie die weiteren Tatsachenvorbringen, die im angefochtenen Urteil keine Stütze finden, nicht berücksichtigt werden. Entgegen der Meinung der Beschwerdeführerin hat das Appellationsgericht für die Frage, ob überhaupt Unterlagen bestehen, nicht auf das Exequaturverfahren verwiesen, sondern mit freier Kognition über die Existenz der Unterlagen entschieden, so dass der Einwand einer Verletzung von <ref-law> an der Sache vorbei geht. Wenn die Vorinstanz gestützt auf seine Tatsachenfeststellungen bzw. die Existenz der Unterlagen entschieden hat, die Beschwerdeführerin sei von der Auskunftspflicht nicht befreit, ist dies nicht zu beanstanden.
3.6 Nach Auffassung der Beschwerdeführerin fehlt es sodann der Beschwerdegegnerin nach schweizerischem Auftragsrecht an einem Informationsinteresse. Soweit sie sich in diesem Zusammenhang auf ihre Noveneingabe vom 12. Juni 2009 beruft, kann sie nicht gehört werden, da - wie dargelegt - diese unberücksichtigt bleiben durfte (E. 3.3). Sodann steht fest, dass die Beschwerdegegnerin den auftragsrechtlichen Anspruch auf Rechenschaftsablegung von ihrem Vater geerbt hat, und hierfür schweizerisches (und nicht französisches) Recht massgebend ist. Entgegen ihrer Darstellung vermag sodann das Argument, die vorliegend in Rede stehenden Beträge seien im Verhältnis zum Gesamtvermögen der Eltern A._/B._ "absolut untergeordnet", das Auskunftsinteresse bzw. den Anspruch nicht in Frage zu stellen. Weiter kritisiert die Beschwerdeführerin, aus dem angefochtenen Urteil gehe nicht klar hervor, dass keine Belege von Drittkonti oder diesbezüglich keine weitere Informationen herauszugeben seien. Der Einwand geht fehl. Die Vorinstanz hat festgehalten, dass die Beschwerdegegnerin ein Interesse betreffend Dritte nur insoweit habe, als sie in einer Beziehung zu ihrem Vater gestanden hätten und die Parteien (A._ und Dritte) über die Beschwerdeführerin Geschäfte bzw. Zahlungen abgewickelt hätten. Dass die Beschwerdeführerin insoweit zur Auskunftserteilung über die Drittkonti selber oder zur Edition von betreffenden Unterlagen verpflichtet sei, lässt sich weder den Erwägungen noch dem Urteilsspruch entnehmen. Die Beschwerdeführerin macht in diesem Zusammenhang vergeblich geltend, die Vorinstanz habe die Auskunftspflicht zu Unrecht auf Konti Dritter ausgedehnt. Zur Rechenschaftsablegung gehört auch die Bekanntgabe der Namen Dritter, mit denen kontrahiert wurde (Fellmann, a.a.O., N. 31 zu Art. 400; vgl. ferner JEANDIN, La production de pièces protégées par le secret bancaire en procédure civile, in: Journée 2002 de droit bancaire et financier, 2003, S. 135, betreffend die Auskunftsklage gemäss <ref-law>). Dies stellt die Beschwerdeführerin selber nicht in Frage, zumal sie festhält, die Beschwerdegegnerin könne Auskunft über Namen und Adressen von Dritten fordern. Insofern sind den Rügen einer Bundesrechtsverletzung kein Erfolg beschieden.
4. Schliesslich wirft die Beschwerdeführerin der Vorinstanz eine Verletzung von <ref-law> vor, soweit sie durch das angefochtene Urteil bzw. das bestätigte erstinstanzliche Urteil verpflichtet wird (vgl. Lit. A), über Vermögenswerte Auskunft zu geben, an welchen A._ lediglich wirtschaftlich berechtigt gewesen ist. Ein entsprechender Anspruch sei nach französischem Erbrecht zu prüfen.
4.1 Der wirtschaftlich Berechtigte hat kein vertragliches Recht gegenüber z.B. einer Bank, Auskunft über den Stand eines Kontos zu erhalten, welches von einem Dritten für ihn bei der Bank gehalten wird (vgl. Urteil 4C.108/2002 vom 23. Juli 2002 E. 3c/aa, in: Pra 2003 Nr. 51 S. 244 ff.; vgl. bereits <ref-ruling> E. 8 S. 211/212 und E. 9 S. 215). Nach der Rechtsprechung geht (dementsprechend) der Anspruch des Erben gegenüber einer Bank, Auskunft über Vermögenswerte, an denen der Erblasser lediglich wirtschaftlich berechtigt war, nicht aus dem Auftrags-, sondern Erbrecht hervor (BGE 4A_421/2009 vom 26. Juli 2010 E. 4). In der Lehre wird bestätigt, dass die Pflicht des Beauftragten, einem pflichtteilsberechtigten Erben Auskunft über Vermögenswerte des Erblassers zu geben, an welcher dieser wirtschaftlich berechtigt war, im Erbrecht gründet (CHAPPUIS, L'utilisation de véhicules successoraux dans un contexte international et la lésion de la réserve successorale, SJ 2005 II S. 60; LOMBARDINI, Actions en reddition de comptes: Quelques développements recents, NRCP 2006, S. 21/22; vgl. ferner STANISLAS, Ayant droit économique et droit civil: le devoir de renseignement de la banque, in: SJ 1999 II S. 448, sowie JACQUEMOUD-ROSSARI, Reddition de comptes et droit aux renseignements, SJ 2006 II S. 33, m.H. zur kantonalen Rechtsprechung). Die Beschwerdeführerin hält zutreffend fest, dass der betreffende Auskunftsanspruch sich in diesem Punkt nicht auf <ref-law> stützt bzw. sich die Beschwerdegegnerin insoweit nicht als Rechtsnachfolgerin des Verstorbenen (A._) auf einen Auskunftsanspruch gegenüber der Beschwerdeführerin berufen kann, sondern einen erbrechtlichen Auskunftsanspruch benötigt.
4.2 Letzter Wohnsitz der Eltern der Beschwerdegegnerin war in Frankreich. Die Beschwerdeführerin selber stellt die internationale Zuständigkeit der schweizerischen Gerichte für die vorliegende Auskunftsklage, soweit sie einzig erbrechtlich zu qualifizieren ist, nicht in Frage. Das Abweichen von der Zuständigkeit am letzten Wohnsitz des Erblassers (vgl. <ref-law>) für die vorliegende Auskunftsklage ist nicht weiter zu erörtern, zumal in dieser rein vermögensrechtlichen Streitigkeit auch Zuständigkeiten nach <ref-law> begründet werden können, wenn - wie hier, wo die Beschwerdegegnerin einzige Erbin ist - andere am Nachlass interessierte Personen nicht berührt sind (Schnyder/Liatowitsch, in: Basler Kommentar Privatrecht, Internationales Privatrecht, 2. Aufl. 2007, N. 19 und 20 zu Art. 86).
4.3 Die Beschwerdeführerin geht selber davon aus, dass sich das erbrechtliche Auskunftsrecht nach französischem Recht als Erbstatut richtet (vgl. Art. 91 Abs. 1, <ref-law>; CHAPPUIS, a.a.O., S. 54; SCHNYDER/LIATOWITSCH, a.a.O., N. 5 zu Art. 92). Dass die Beschwerdegegnerin als pflichtteilsberechtigte Erbin und durch Universalsukzession die Vermögenswerte ihrer Eltern erworben hat, ist unbestritten. Sie macht allerdings geltend, die Beschwerdegegnerin habe nach französischem Recht gar keinen erbrechtlichen Auskunftsanspruch. Die Richtigkeit ihrer Ausführungen ist fraglich. Immerhin gilt nach französischem Recht gemäss der Rechtsprechung zu Art. 10 des französischen Code Civil (fr.CC), dass ein Dritter, z.B. eine Bank den Erben Auskunft über die Vermögenswerte des Erblassers zu geben hat (vgl. Hinweise in: HENRY u.a., Méga Code civil, 8. Aufl. Dalloz, Paris 2009, N. 103 zu Art. 10). Auch die Bedenken der Beschwerdeführerin zur (materiellen oder prozessualen) Rechtsnatur des Auskunftsanspruchs eines Erben gemäss französischem Recht sind wenig nachvollziehbar. Der - hierfür massgebende - Verweisungsbegriff in <ref-law> umfasst erbrechtliche Auskunftsrechte, worunter das Auskunftsrecht der Erben gemäss Art. 10 fr.CC fällt, zumal nach französischem Erbrecht die pflichtteilsberechtigten Erben ohne weiteres dazu berufen sind, die zum Nachlass gehörenden Vermögenswerte zusammenzutragen (TERRÉ/LEQUETTE, Droit civil, Les successions, Les libéralités, 3. Aufl., Paris 1997, Rz. 498 S. 489). Ob die Beschwerdegegnerin einen erbrechtlichen Auskunftsanspruch hat, kann jedoch - wie sich aus dem Folgenden ergibt - vom Bundesgericht nicht überprüft werden.
4.4 Das Appellationsgericht hat überhaupt nicht geprüft, ob die Beschwerdegegnerin gestützt auf das französische Erbrecht einen Auskunftsanspruch gegenüber der Beschwerdeführerin hat, obwohl dies bereits im kantonalen Verfahren umstritten war. Vielmehr ist es davon ausgegangen, dass die Pflicht, einem pflichtteilsberechtigten Erben Auskunft über Vermögenswerte des Erblassers zu geben, sich einzig und umfassend auf das schweizerische Vertragsstatut stützen lässt. Diese Auffassung ist - wie dargelegt - betreffend die Vermögenswerte, an welchen der Erblasser lediglich wirtschaftlich berechtigt war, unzutreffend. Wenn die Beschwerdeführerin vorbringt, ein entsprechender Auskunftsanspruch müsse in Anwendung von französischem Recht geprüft werden, rügt sie, dass ausländisches Recht nicht angewendet worden ist, wie es das schweizerische internationale Privatrecht vorsieht (<ref-law>). Diese Rüge ist begründet und die Beschwerde insoweit gutzuheissen.
4.5 Nach dem Dargelegten kommt die Vorinstanz nicht darum herum, für das Begehren, die Beschwerdeführerin habe Aufschluss auch über Vermögenswerte von A._ und/oder B._ zu erteilen, an welchen diese wirtschaftlich berechtigt waren, den Auskunftsanspruch der Beschwerdegegnerin nach französischem Erbrecht zu prüfen.
5. Aus diesen Gründen ist die Beschwerde in Zivilsachen teilweise gutzuheissen und das angefochtene Urteil aufzuheben. Die Sache wird im Sinne der Erwägungen zur Anwendung des massgeblichen ausländischen Rechts (E. 4.5) an die Vorinstanz zu neuer Entscheidung zurückgewiesen. Bei diesem Verfahrensausgang haben die Parteien die Verfahrenskosten je zur Hälfte zu tragen und werden die Parteikosten wettgeschlagen (Art. 66 Abs. 1 und Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird teilweise gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 17. Juni 2009 wird aufgehoben. Die Sache wird zu neuer Entscheidung im Sinne der Erwägungen an das Appellationsgericht zurückgewiesen.
2. Die Gerichtskosten von Fr. 5'000.-- werden der Beschwerdeführerin und der Beschwerdegegnerin je zur Hälfte auferlegt.
3. Die Parteikosten werden wettgeschlagen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 13. September 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Levante