Sachverhalt:
A. Mit letztwilliger Verfügung vom 12. Mai 1999 bestimmte A._ die A._-Stiftung mit Sitz in B._ zu seiner Erbin. Seine Ehefrau X._ und seine Tochter C._ setzte er auf den Pflichtteil und legte die ihnen zukommenden Anteile mittels Teilungsvorschriften fest. Zudem richtete er mit letztwilliger Verfügung vom 22. April 2002 eine Reihe von Vermächtnissen aus. In seinem Testament vom 9. Mai 2003 ernannte er Y._ als Willensvollstrecker.
Am 19. Mai 2003 verstarb A._ an seinem letzten Wohnsitz in D._.
B. Mit Beschwerde vom 8. Februar 2007 verlangte X._ im Wesentlichen die Absetzung von Y._ als Willensvollstrecker und die Anordnung einer Erbschaftsverwaltung; eventualiter beantragte sie dessen Suspendierung und subeventualiter den Erlass von richterlichen Weisungen an den Willensvollstrecker. Zur Begründung führte sie aus, der Willensvollstrecker sei gleichzeitig Stiftungsrat der vom Erblasser gegründeten A._-Stiftung und befinde sich deshalb in einem unlösbaren Interessenkonflikt: Einerseits müsste er als Willensvollstrecker bestrebt sein, alle Nachlasswerte festzustellen und insbesondere die nicht deklarierten Vermögenswerte des Erblassers, die vermutungsweise über Trusts gehalten würden, zur Nachlassmasse zu ziehen; andererseits habe er als Stiftungsrat ein Interesse daran, dass die undeklarierten Vermögenswerte nicht aufgefunden würden. Er habe die hängige Erbschaftsklage gegen die Anstalten F._ und G._ von K._ immer wieder verzögert, er habe sich geweigert, in K._ gegen mutmassliche Informationsträger auf Auskunft über die nicht deklarierten Vermögenswerte zu klagen, und er habe auch in anderer Hinsicht nicht genügend nach den undeklarierten Werten gesucht.
Mit Verfügung vom 11. Juli 2008 wies das Bezirksgericht L._ die Beschwerde ab und verpflichtete X._ zu einer Gerichtsgebühr von Fr. 584'888.-- und einer Entschädigung von Fr. 379'163.-- zzgl. MwSt an den Willensvollstrecker; es ging dabei von einem Streitwert von Fr. 89,83 Mio. aus (Wert der nicht deklarierten Vermögenswerte gemäss Angaben der Beschwerdeführerin von Fr. 92 Mio., abzüglich Nachsteuern von Fr. 10,5 Mio., zuzüglich Darlehen von Fr. 8,33 Mio., welches die Beschwerdeführerin mit der Beschwerde erzwingen wollte).
In teilweiser Gutheissung der Kostenbeschwerde gegen die Gerichtskosten und des Rekurses gegen die Parteientschädigung setzte das Obergericht des Kantons Zürich mit Beschluss vom 8. Dezember 2008 die erstinstanzliche Gerichtsgebühr auf Fr. 450'000.-- und die Parteientschädigung auf Fr. 320'000.-- zzgl. MwSt fest; es ging dabei von einem Streitwert von Fr. 118 Mio. aus, modifizierte aber gegenüber der ersten Instanz die nach der Gebührenordnung möglichen Zu- und Abschläge.
C. Gegen den Beschluss des Obergerichts hat X._ am 7. Januar 2009 Beschwerde in Zivilsachen eingereicht mit den Begehren um Festsetzung der erstinstanzlichen Gerichtsgebühr auf Fr. 23'062.50 oder auf einen Betrag nach Ermessen des Bundesgerichtes, eventuell um Rückweisung der Sache an das Obergericht.
Mit Präsidialverfügung vom 16. Januar 2009 wurde der Beschwerde die aufschiebende Wirkung erteilt.
Das Obergericht hat auf das Einreichen einer Vernehmlassung verzichtet.

Erwägungen:
1. Angefochten ist die kantonal letztinstanzliche (<ref-law> i.V.m. <ref-law>/ZH) Festsetzung der Gerichtsgebühr in einem Aufsichtsverfahren gegen den Willensvollstrecker, mithin in einer öffentlich-rechtlichen Streitigkeit in unmittelbarem Zusammenhang mit dem Zivilrecht (Art. 72 Abs. 2 lit. b Ziff. 5 BGG; Urteil 5A_646/2008 vom 22. Dezember 2008, E. 1.1). Der Streitwert von Fr. 30'000.-- (<ref-law>) ist offensichtlich erreicht.
2. In verschiedener Hinsicht rügt die Beschwerdeführerin eine Verletzung des rechtlichen Gehörs; wegen dessen formeller Natur ist diese Rüge vorweg zu prüfen (<ref-ruling> E. 2a S. 232; <ref-ruling> E. 4a S. 469).
2.1 Die Beschwerdeführerin behauptet, es sei ihr keine Gelegenheit zur Stellungnahme eingeräumt worden, insbesondere nicht dazu, dass das Obergericht der Gebührenfestsetzung den Nachlasswert zugrunde gelegt habe.
Die Rüge geht fehl: Das oberinstanzliche Verfahren hatte ausschliesslich die Kosten- und Entschädigungsfestsetzung zum Gegenstand. Die Beschwerdeführerin hat sich mit Beschwerde und Replik zweimal umfassend geäussert. Dabei hat sie sich bereits in ihrer Beschwerde ausführlich zur Praxis des Obergerichts, wonach bei Streitigkeiten um den Willensvollstrecker für die Streitwertfestsetzung in der Regel vom Nachlasswert ausgegangen wird, Bezug genommen und die betreffende Praxis kritisiert. Diese war der Beschwerdeführerin mithin bekannt, und sie hat dazu, wie festgehalten, ausführlich Stellung genommen.
2.2 Die Beschwerdeführerin rügt wiederholt eine Verletzung der Begründungspflicht als Teilgehalt des rechtlichen Gehörs.
Die Begründung eines Entscheides muss so abgefasst sein, dass der Betroffene ihn gegebenenfalls sachgerecht anfechten kann. Dies ist nur möglich, wenn sowohl er wie auch die Rechtsmittelinstanz sich über die Tragweite des Entscheids ein Bild machen können. In diesem Sinn müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf welche sich ihr Entscheid stützt. Es ist jedoch nicht nötig, dass sich die Behörde mit jeder tatsächlichen Behauptung und mit jedem rechtlichen Einwand auseinandersetzt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 3.2 S. 236; <ref-ruling> E. 3.3 S. 455; <ref-ruling> E. 4.1 S. 88).
Der angefochtene Entscheid setzt sich mit allen wesentlichen Vorbringen der Beschwerdeführerin auseinander. Er nennt die zentralen Überlegungen, von denen das Obergericht ausgegangen ist, und diese werden in jeder Hinsicht verständlich und nachvollziehbar ausgeführt. Wie ihre 50-seitige Beschwerde zeigt, war die Beschwerdeführerin denn auch ohne weiteres in der Lage, den Entscheid des Obergerichts sachgerecht anzufechten. Die Rüge ist demnach unbegründet.
3. Die Beschwerdeführerin rügt eine Verletzung des Legalitätsprinzips.
Das Erfordernis der gesetzlichen Grundlage im Abgaberecht ist ein selbständiges verfassungsmässiges Recht, dessen Verletzung unmittelbar gestützt auf <ref-law> angerufen werden kann (<ref-ruling> E. 4.1 S. 120).
In der Begründung ihrer Rüge vermischt die Beschwerdeführerin freilich die gesetzliche Grundlage mit dem sich aus dieser Grundlage ergebenden Resultat: Sie anerkennt ausdrücklich die Gesetzmässigkeit der angewandten kantonalen Gebührenverordnung (Rz. 30), kritisiert aber die Höhe der Gerichtsgebühr im Ergebnis als ungesetzlich. Die Höhe der Gerichtsgebühr hängt indes davon ab, ob eine vermögensrechtliche oder nicht vermögensrechtliche Streitigkeit vorliegt (dazu E. 6.3), und letzterenfalls massgeblich von der Höhe des Streitwertes, sieht doch die vom Obergericht zur Anwendung gebrachte Gebührenverordnung (dazu E. 6.2) für die vermögensrechtlichen Verfahren einen streitwertabhängigen Tarif vor.
Einzig insofern weist die konkrete Höhe der Gerichtsgebühr indirekt einen Zusammenhang mit dem Legalitätsprinzip auf, als an die Regelungsdichte der delegierenden Gesetzesnorm tiefere Anforderungen gestellt werden können, wo das Kostendeckungs- und Äquivalenzprinzip das Mass der Abgabe begrenzt (<ref-ruling> E. 2.2 S. 116). Dass keine genügende Delegationsnorm vorhanden wäre, macht die Beschwerdeführerin freilich zu Recht nicht geltend (siehe E. 6.2).
4. Die Beschwerdeführerin rügt eine Verletzung ihres Anspruchs auf "wohlfeile Erledigung des Verfahrens" (§ 18 Abs. 1 KV/ZH).
Sie legt aber nicht dar, welche Ansprüche sie aus § 18 KV/ZH konkret ableitet, weshalb ihre Rüge unsubstanziiert bleibt. Ohnehin wird der verfassungsrechtliche Gehalt der betreffenden Bestimmung durch die kantonale Gesetzgebung umgesetzt bzw. präzisiert und muss der angefochtene Kostenentscheid im Einzelnen vor dieser standhalten. Darauf wird im Sachzusammenhang zurückzukommen sein.
5. Unzutreffend ist sodann die Behauptung, selbst die Erben eines wohlhabenden Erblassers vermöchten keine so hohen Gerichtsgebühren zu bezahlen, was den Zugang zum Gericht faktisch verunmögliche (Art. 6 EMRK und <ref-law>), besteht doch bei gegebenen Voraussetzungen ein Anspruch auf unentgeltliche Rechtspflege, deren Zielsetzung gerade die Ermöglichung des freien Zugangs zum Gericht unabhängig von der finanziellen Situation ist (<ref-ruling> E. 3.1 S. 355). Vorliegend legt aber die Beschwerdeführerin ihre Einkommens- und Vermögensverhältnisse ohnehin nicht offen, und sie zeigt auch nicht auf, inwiefern ihr angesichts ihrer konkreten persönlichen bzw. finanziellen Situation der Zugang zum Gericht verbaut sein soll.
6. In der Sache selbst behauptet die Beschwerdeführerin eine willkürliche Handhabung der massgeblichen kantonalen Grundlagen für die Festsetzung der Gerichtsgebühr sowie im Speziellen eine Verletzung des Äquivalenzprinzips.
6.1 Mit Beschwerde in Zivilsachen kann insbesondere die Verletzung von Bundesrecht, Völkerrecht und kantonaler verfassungsmässiger Rechte geltend gemacht werden (<ref-law>). Kantonales Recht ist - unter Vorbehalt von Art. 95 lit. c und d BGG - vom Bundesgericht grundsätzlich nicht zu überprüfen. Das Obergericht hat sich bei der Festsetzung der Gerichtskosten auf die kantonale Verfahrensordnung sowie auf das verfassungsrechtliche Äquivalenzprinzip abgestützt. Dieses konkretisiert das Verhältnismässigkeitsprinzip und das Willkürverbot für den Bereich der Kausalabgaben (<ref-ruling> E. 2.3 S. 228). Die Frage der Verhältnismässigkeit kann ausserhalb des Schutzbereichs spezieller Grundrechte nur unter dem Gesichtswinkel des Willkürverbots geprüft werden (<ref-ruling> E. 4.2.2 S. 158). Es kann somit geltend gemacht werden, die konkrete Anwendung des kantonalen Rechts habe das Willkürverbot gemäss <ref-law> oder andere verfassungsmässige Rechte verletzt (<ref-ruling> E. 2.3 S. 466).
6.2 Gemäss § 64 Abs. 1 und 2 ZPO/ZH bemessen sich die in der Regel der unterliegenden Partei aufzuerlegenden Gerichtskosten nach den Bestimmungen des Gerichtsverfassungsgesetzes. In § 202 Abs. 1 GVG/ZH wird die Verordnungskompetenz für die Gebühren- und Entschädigungsansätze an das Obergericht delegiert, welches am 4. April 2007 die vorliegend massgebende Verordnung über die Gerichtsgebühren erlassen hat (GebV, LS 211.11).
Bei nicht vermögensrechtlichen Streitigkeiten beträgt die Gerichtsgebühr aufgrund des tatsächlichen Streitinteresses, des Zeitaufwandes und der Schwierigkeit des Falles zwischen Fr. 300.-- und 13'000.-- (§ 4 Abs. 3 GebV). Für vermögensrechtliche Streitigkeiten sieht § 4 Abs. 1 GebV einen streitwertabhängigen Tarif vor. Sie kann um bis zu einem Drittel, in Ausnahmefällen auch um mehr, erhöht oder insbesondere bei periodisch wiederkehrenden Leistungen ermässigt werden (§ 4 Abs. 2 GebV). Im summarischen Verfahren beträgt die Gebühr zwei Drittel bis drei Viertel des so berechneten Betrages (§ 7 GebV).
Gemäss <ref-law>/ZH richtet sich der Streitwert nach dem Rechtsbegehren des Klägers zur Zeit des Eintritts der Rechtshängigkeit. Geht die Klage nicht auf Geldzahlung, ist der Wert massgebend, welchen die Parteien dem Streitgegenstand übereinstimmend beilegen (<ref-law>/ZH). Sind die Parteien nicht einig, bestimmt das Gericht den Streitwert nach freiem Ermessen; in der Regel ist der höhere Betrag massgebend (<ref-law>/ZH).
6.3 Das Obergericht ist von einer vermögensrechtlichen Streitigkeit ausgegangen, was die Beschwerdeführerin für willkürlich hält. Sie macht geltend, es sei ihr mit der Willensvollstreckerbeschwerde bloss um Transparenz bezüglich der finanziellen Situation bzw. um die Speisung der A._-Stiftung durch saubere Mittel gegangen, ferner auch um die Erledigung des Steuerstrafverfahrens, um den Schutz des Rufes des Erblassers und um die Vermeidung einer "black box". All dies seien nicht vermögenswerte, sondern ideelle Ziele.
Vorab liesse sich fragen, ob die Willkürrüge nicht bereits daran scheitert, dass erbrechtliche Angelegenheiten naturgemäss nicht ideeller, sondern vermögensrechtlicher Art sind. Weiter ist darauf hinzuweisen, dass das Bundesgericht in seiner publizierten Rechtsprechung sowohl den Ausschluss aus einer Stockwerkeigentümergemeinschaft (<ref-ruling> E. 1 S. 17) und die Anfechtung von Beschlüssen der Stockwerkeigentümergemeinschaft schlechthin (<ref-ruling> E. 1b S. 79 f.) als auch die Anfechtung von Generalversammlungsbeschlüssen einer Aktiengesellschaft (<ref-ruling> E. 1 S. 181) und das Gesuch um Einsetzung eines Sonderprüfers (<ref-ruling> E. 2 S. 395; <ref-ruling> E. 1.2.2 S. 304) als vermögensrechtlich ansieht. Was den Willensvollstrecker im Speziellen anbelangt, hat das Bundesgericht im Urteil 5A_646/2008 vom 22. Dezember 2008, E. 2.3, ausdrücklich entschieden, dass die Annahme, ein Streit um dessen Absetzung sei vermögensrechtlicher Natur, nicht als willkürlich angesehen werden kann. Von einer vermögensrechtlichen Streitigkeit geht auch die Lehre aus (vgl. Poudret/ Sandoz-Monod, Commentaire de la loi fédérale d'organisation judiciaire, Band II, Bern 1990, S. 16 und 233).
Im vorliegenden Fall stehen direkte finanzielle Interessen sogar besonders stark im Vordergrund. Anlass und Zweck der Willensvollstreckerbeschwerde war, dass die Beschwerdeführerin zusätzliche Vermögenswerte von ca. 90 Mio. in die Nachlassmasse holen will und der Willensvollstrecker nach ihrer Auffassung diese Pläne zu durchkreuzen versucht. Sie verfolgt somit keine ideellen, sondern vermögensrechtliche Interessen. Die Willensvollstreckerbeschwerde durfte mithin willkürfrei als vermögensrechtliche Streitigkeit qualifiziert und ihr ein Streitwert beigemessen werden.
6.4 Was dessen Höhe anbelangt, hat das Obergericht erwogen, weder könnten die vom Willensvollstrecker erbrachten bzw. zu erbringenden Leistungen massgeblich sein, stehe doch weit mehr als nur dessen Honorar auf dem Spiel, noch der Erbteil der Beschwerdeführerin, ansonsten sich der Streitwert laufend ändern würde, je nachdem, welcher Erbe die Beschwerde einreiche. Umso weniger könne dies im vorliegenden Fall relevant sein, wo die Beschwerdeführerin im Hauptpunkt die Absetzung des Willensvollstreckers verlangt habe, was die Abwicklung des gesamten Nachlasses betreffe und sich auf sämtliche Erben gleichermassen auswirke. Eine Amtsführung, der nur durch die Absetzung des Willensvollstreckers begegnet werden könne, gefährde regelmässig den Nachlass als Ganzes, und deshalb bilde in solchen Fällen der (sich gemäss Verfügung der Finanzdirektion des Kantons Zürich vom 11. März 2008 auf Fr. 118'564'675.-- belaufende) Nachlasswert die wirtschaftliche Tragweite der Willensvollstreckerbeschwerde am besten ab.
6.5 Die Beschwerdeführerin erachtet es als willkürlich, dass das Obergericht für die Streitwertberechnung den Nachlasswert als Grundlage genommen hat.
In der Tat ist im vorliegenden Fall nicht der Nachlass, sondern die Absetzung des Willensvollstreckers Streitgegenstand. Entsprechend ist der Nachlasswert als solcher ein sachfremdes Kriterium im Zusammenhang mit der Beurteilung (einzig und spezifisch) der Absetzungsfrage. Dass es unhaltbar und damit willkürlich ist, den Nachlasswert als Streitwert im Absetzungsverfahren anzunehmen, zeigt sich insbesondere auch darin, dass es im Zuge der Erbschaftsabwicklung ohne weiteres zu stets neuen Beschwerden, ja auch zu mehreren Absetzungsbegehren kommen kann, während im ganzen Bereich des Zivilrechts in der Sache selbst typischerweise ein einziges materielles Urteil gefällt wird.
Im vorliegenden Fall darf aber im Zusammenhang mit der Absetzung selbstverständlich die hinter dieser Frage stehende grosse (finanzielle) Tragweite berücksichtigt werden: Wie erwähnt geht es der Beschwerdeführerin letztlich darum, mit der personellen Ersetzung des Willensvollstreckers umfangreiche Vermögenswerte in die Nachlassmasse zu holen. Die Behauptung der Beschwerdeführerin, sie habe von der Gutheissung der Beschwerde keinen oder nur einen geringen finanziellen Nutzen erwartet, ist deshalb falsch. Unzutreffend ist auch die Behauptung, es sei ihr gar nicht um eine Absetzung des Willensvollstreckers gegangen, sie habe die Ersetzung durch einen Erbschaftsverwalter nur als "ultima ratio" angesehen: Die Beschwerdeführerin hat erstinstanzlich als Hauptbegehren die Absetzung des Willensvollstreckers und Ersetzung durch einen Erbschaftsverwalter, eventualiter eine Einstellung des Willensvollstreckers im Amt und subeventualiter die nach Ermessen des Einzelrichters zum Schutz des Nachlasses und der Interessen der Erben erforderlichen Weisungen verlangt. Diese Rechtsbegehren, welche die Beschwerdeführerin selbst gestellt hat, muss sie sich entgegenhalten lassen. Gleichwohl bleibt es dabei, dass eine Gerichtsgebühr von Fr. 450'000.-- für das Absetzungsverfahren eines Willensvollstreckers unhaltbar ist und damit <ref-law> verletzt.
Die Kostenfestsetzung ergeht vorliegend gestützt auf kantonales Recht und der Kanton geniesst bei der Bemessung der Gerichtsgebühr einen weiten Spielraum, der einzig durch das Willkürverbot bzw. die aus ihm abgeleiteten Prinzipien begrenzt ist. Es würde daher nicht angehen, dem Obergericht über die vorstehend genannten Anhaltspunkte hinaus konkrete Vorgaben für die Neufestsetzung der Gerichtsgebühr zu machen. Es sei einzig erwähnt, dass es im Rahmen des weiten kantonalen Ermessens und aufgrund des aufsichtsrechtlichen Charakters des kantonalen Verfahrens durchaus auch zulässig wäre, sich statt an der Verordnung des Obergerichts über die Gerichtsgebühren an derjenigen des Verwaltungsgerichts zu orientieren (LS 175.252); nach deren § 3 kann die Gerichtsgebühr bei Streitwerten über Fr. 1'000'000.-- bis Fr. 50'000.-- betragen, und dieser Betrag kann gemäss § 5 bei besonders aufwändigen Verfahren bis auf den doppelten Betrag erhöht werden.
6.6 Angesichts der vorstehenden Erwägungen, die zu einer Aufhebung des angefochtenen Entscheides führen, werden die Fragen rund um die Äquivalenz im engeren Sinn gegenstandslos, muss doch vielmehr die neu festgesetzte Gerichtsgebühr vor dem Äquivalenzprinzip standhalten. Soweit die Beschwerdeführerin geltend macht, der erstinstanzliche Richter habe unnötigen Aufwand betrieben, sei immerhin bemerkt, dass sie erwarten durfte, dass sich der erstinstanzliche Richter ernsthaft mit ihrer knapp 200-seitigen Beschwerde und ihren verschiedenen weiteren Eingaben (namentlich 30-seitige Eingabe vom 14. Juni 2007 und über 100-seitige Eingabe vom 23. Juni 2008) sowie mit der über 200-seitigen Beschwerdeantwort und den weiteren Stellungnahmen beschäftigen würde. Sodann hat sie die umfangreichen Beilagen offensichtlich mit dem Zweck eingereicht, dass sie zur Kenntnis genommen würden; wenn der erstinstanzliche Richter genau dies getan hat, kann die Beschwerdeführerin nicht ernsthaft behaupten, dieser habe zu viel Aufwand betrieben und der 125-seitige Entscheid sei unnötig bzw. unangemessen gewesen.
7. Zusammenfassend erweist es sich als willkürlich, im Zusammenhang mit der Absetzung eines Willensvollstreckers den Nachlasswert als Streitwert einzusetzen, und die Festsetzung der erstinstanzlichen Gerichtsgebühr auf Fr. 450'000.-- hält im vorliegenden Fall nicht vor dem Willkürverbot stand. Der angefochtene Entscheid ist demzufolge aufzuheben und das Obergericht hat neu über die Gebührenfrage zu entscheiden.
Die Beschwerdeführerin ist im Grundsatz durchgedrungen, weshalb es sich rechtfertigt, den unterliegenden und in seinen finanziellen Interessen betroffenen Kanton Zürich als kosten- und entschädigungspflichtig zu erklären (Art. 66 Abs. 1 und 4 sowie <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird gutgeheissen und der Beschluss des Obergerichts des Kantons Zürich, II. Zivilkammer, vom 8. Dezember 2008 wird aufgehoben.
2. Die Gerichtskosten von Fr. 8'000.-- werden dem Kanton Zürich auferlegt.
3. Der Kanton Zürich hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 10'000.-- zu entschädigen.
4. Dieses Urteil wird der Beschwerdeführerin, dem Obergericht des Kantons Zürich, II. Zivilkammer, und dem Kassationsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 20. Mai 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Möckli