Sachverhalt:
A. A.a Der Wohlfahrtsfonds A._, die Stiftung B._, die Stiftung C._, der Wohlfahrtsfonds D._ sowie die Pensionskasse E._ (nachfolgend: Vorsorgewerke E._) besassen per Ende Dezember 2003 insgesamt einen Bestand von 725'000 Inhaberaktien à nominal Fr. 1.-- der X._ Holding AG.
A.b Im Januar 2004 kontaktierte die Y._ Bank die Vorsorgewerke E._ und fragte an, ob diese bereit wären, einen Teil ihrer X._-Aktien zum Zwecke der Kapitalherabsetzung der X._ Holding anzudienen. Die Vorsorgewerke E._ erklärten sich in der Folge bereit, Aktien aus den bisherigen Beständen anzudienen, wollten aber wieder einen gleichen Bestand von X._-Aktien erwerben.
X._ Holding und Y._ Bank standen in den Jahren 2003 und 2004 in einem Mutter-Tochter-Verhältnis mit hundertprozentiger Beherrschung durch die X._ Holding.
Am 12. Januar 2004 verkaufte die Y._ Bank der Pensionskasse E._, der Stiftung C._ sowie dem Wohlfahrtsfonds A._ insgesamt 195'000 X._-Aktien zum Marktpreis von Fr. 84.35 je Aktie. Am 20. Januar 2004 kaufte die Y._ Bank im Namen und auf Rechnung der X._ Holding 195'000 X._-Aktien zum Preis von Fr. 84.75 je Aktie von der Pensionskasse E._, der Stiftung C._ und dem Wohlfahrtsfonds A._ zurück. Die Y._ Bank rechnete dabei auf dem Verkaufspreis (nach Abzug des Nominalwerts von Fr. 1.-- pro Aktie) jeweils eine Verrechnungssteuer von 35 % ab. Im Einzelnen stellte sich dies wie folgt dar:
Pensionskasse E._: 170'000 Aktien; Verkaufspreis Fr. 14'407'500.--; Verrechnungssteuer Fr. 4'983'125.--.
Stiftung C._: 10'000 Aktien; Verkaufspreis Fr. 847'500.--; Verrechnungssteuer Fr. 293'125.--.
Wohlfahrtsfonds A._: 15'000 Aktien; Verkaufspreis Fr. 1'271'250.--; Verrechnungssteuer Fr. 439'687.50.
Die X._ Holding vernichtete die oben erwähnten 195'000 Inhaberaktien am 18. Februar 2004 im Rahmen einer Kapitalherabsetzung.
A.c Im Verlauf des Jahres 2004 kontaktierte die Y._ Bank erneut die Vorsorgewerke E._ und und fragte an, ob diese bereit wären, einen Teil ihrer X._-Aktien zum Zwecke der Kapitalherabsetzung der X._ Holding anzudienen. Die Vorsorgewerke E._ erklärten sich wiederum bereit, Aktien aus den bisherigen Beständen anzudienen, mit der Absicht, wieder einen gleichen Bestand von X._-Aktien zu erwerben.
A.d Am 19. Juli 2004 verkaufte die Y._ Bank den Vorsorgewerken E._ insgesamt 500'000 X._-Aktien zum Marktpreis von Fr. 77.-- je Aktie. Am gleichen Tag kaufte die Y._ Bank im Namen und auf Rechnung der X._ Holding insgesamt 500'000 X._-Aktien zum Preis von Fr. 78.-- je Aktie von den Vorsorgewerken E._ zurück. Die Y._ Bank rechnete dabei auf dem Verkaufspreis (nach Abzug des Nominalwerts von Fr. 1.-- pro Aktie) wiederum jeweils eine Verrechnungssteuer von 35 % ab. Im Einzelnen stellte sich dies wie folgt dar:
Pensionskasse E._: 410'000 Aktien; Verkaufspreis Fr. 31'980'000.--; Verrechnungssteuer Fr. 11'049'500.--.
Stiftung C._: 50'000 Aktien; Verkaufspreis Fr. 3'900'000.--; Verrechnungssteuer Fr. 1'347'500.--.
Stiftung B._: 10'000 Aktien; Verkaufspreis Fr. 780'000.--; Verrechnungssteuer Fr. 269'500.--.
Wohlfahrtsfonds A._: 15'000 Aktien; Verkaufspreis Fr. 1'170'000.--; Verrechnungssteuer Fr. 404'250.--.
Wohlfahrtsfonds D._: 15'000 Aktien; Verkaufspreis Fr. 1'170'000.--; Verrechnungssteuer Fr. 404'250.--.
Die X._ Holding vernichtete die oben erwähnten 500'000 Inhaberaktien am 23. Februar 2005 im Rahmen einer Kapitalherabsetzung.
B. B.a In den Monaten Februar bis Mai 2005 machten die Vorsorgewerke E._ für die vorerwähnten Transaktionen die Rückerstattung der Verrechnungssteuer von insgesamt Fr. 19'190'937.50 geltend. Im Einzelnen stellte sich dies wie folgt dar:
Pensionskasse E._: Sie beantragte am 18. Februar 2005 eine Rückerstattung im Umfang von Fr. 16'032'625.-- (Fr. 4'983'125.-- plus Fr. 11'049'500.--).
Stiftung C._: Sie beantragte am 28. Februar 2005 eine Rückerstattung im Umfang von Fr. 1'640'625.-- (Fr. 293'125.-- plus Fr. 1'347'500.--).
Stiftung B._: Sie beantragte am 27. April 2005 eine Rückerstattung im Umfang von Fr. 269'500.--.
Wohlfahrtsfonds A._: Er beantragte am 2. Mai 2005 eine Rückerstattung im Umfang von Fr. 843'937.50 (Fr. 439'687.50 plus Fr. 404'250.--)
Wohlfahrtsfonds D._: Er beantragte am 28. April 2005 eine Rückerstattung im Umfang von Fr. 404'250.--.
Die Eidgenössische Steuerverwaltung (nachfolgend: ESTV) gab den entsprechenden Anträgen der Vorsorgewerke E._ vollumfänglich statt.
B.b Aufgrund von Abklärungen erhielt die ESTV in der Folge Kenntnis von den vorerwähnten Aktienkäufen und -verkäufen und forderte die Vorsorgewerke E._ mit Schreiben vom 8. Februar 2006 zur Rückzahlung der entsprechenden Rückerstattungsbeträge von insgesamt Fr. 19'190'937.50 auf. Die Vorsorgewerke E._ erklärten mit Schreiben vom 29. Juni 2006, die Rückzahlungen per 28. Juni 2006 erfolgten unter ausdrücklichem Vorbehalt, und der Bestand und die Höhe der Forderungen der ESTV seien in einem Rechtsmittelverfahren abschliessend festzustellen; die Bezahlung stelle keine Anerkennung der geltend gemachten Forderung dar.
B.c Die ESTV beschloss mit (je separat eröffneten) Entscheiden vom 20. Dezember 2006, dass sie den (einzelnen) Vorsorgewerken E._ die Rückerstattung der Verrechnungssteuer im Betrag von insgesamt Fr. 19'190'937.50 auf den (jeweiligen) im Jahr 2004 fällig gewordenen Teilliquidationsanteilen betreffend die Kapitalreduktion der X._ Holding verweigere.
B.d Am 31. Januar 2007 erhoben die Vorsorgewerke E._ gegen die Entscheide der ESTV vom 20. Dezember 2006 (je separat und entsprechend ihren Anteilen) Einsprache und beantragten, ihnen sei die Verrechnungssteuer von insgesamt Fr. 19'190'937.50 zurückzuerstatten, zuzüglich (je) eines Vergütungszinses von 5 % ab 28. Juni 2006.
B.e Mit Entscheid vom 10. Mai 2007 wies die ESTV die Einsprachen vollumfänglich ab und stellte fest, dass die Vorsorgewerke E._ ihr den Betrag von insgesamt Fr. 19'190'937.50 zu Recht zurückvergütet hätten. Zudem stellte die ESTV fest, dass die Vorsorgewerke E._ ihr einen (anteilsmässigen) Verzugszins von 5 % auf diesem Betrag für die Zeitspanne der Rückerstattung bis zum 28. Juni 2006 schuldeten.
Die ESTV begründete diesen Entscheid im Wesentlichen damit, dass die Einsprecher wirtschaftlich nicht frei über die Zahlungen der Y._ Bank vom 20. Januar resp. 14. Juli 2004 hätten verfügen können und ihnen daher das Recht zur Nutzung dieser Zahlungen abzusprechen sei. In der Sache kam die ESTV zum Schluss, es liege eine Steuerumgehung vor.
C. Die gegen diesen Einspracheentscheid am 13. Juni 2007 erhobenen Beschwerden an das Bundesverwaltungsgericht blieben erfolglos. Das Bundesverwaltungsgericht vereinigte zunächst mit Verfügung vom 21. Juni 2007 die verschiedenen Beschwerden und wies diese mit Urteil vom 5. November 2008 ab.
Das Bundesverwaltungsgericht bejahte zwar einen grundsätzlichen Anspruch auf Rückerstattung der Verrechnungssteuer, da die Vorsorgewerke E._ bei Fälligkeit der steuerbaren Leistung das Recht zur Nutzung des den steuerbaren Ertrag abwerfenden Vermögenswertes besessen hätten. Hingegen kam das Bundesverwaltungsgericht zum Schluss, dass eine Rückerstattung der Verrechnungssteuer zu einer Steuerumgehung führen würde, an welcher die Vorsorgewerke E._ massgeblich beteiligt waren.
D. Mit Eingabe vom 17. Dezember 2008 erheben die Vorsorgewerke E._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht und stellen folgenden Hauptantrag:
"Den Beschwerdeführenden sei die Verrechnungssteuer von total CHF 19'190'937.50 auf den im Jahre 2004 fällig gewordenen Teilliquidationsanteilen aus zwei Kapitalherabsetzungen der X._ Holding AG wie folgt zurückzuerstatten:
Wohlfahrtsfonds A._ ein Verrechnungssteuerbetrag von total CHF 843'937.50 (CHF 439'687.50 und CHF 404'250);
Stiftung B._ ein Verrechnungssteuerbetrag von CHF 269'500;
Stiftung C._ ein Verrechnungssteuerbetrag von total CHF 1'640'625 (CHF 293'125 und CHF 1'347'500);
Wohlfahrtsfonds D._ ein Verrechnungssteuerbetrag von CHF 404'250;
Pensionskasse E._ ein Verrechnungssteuerbetrag von total CHF 16'032'625 (CHF 4'983'125 und CHF 11'049'500).
jeweils zuzüglich eines Vergütungszinses ab 28. Juni 2006 von 5 %."
Eventualiter beantragen die Beschwerdeführer, die Sache sei zur Feststellung des massgebenden Sachverhalts an die ESTV zurückzuweisen.
Gerügt wird neben einer unrichtigen Feststellung des Sachverhalts (sinngemäss) die Verletzung von Bundesrecht durch die Vorinstanz, da diese die Mitwirkung der Beschwerdeführer an einer Steuerumgehung bejaht habe.
E. Die Eidgenössische Steuerverwaltung beantragt die Abweisung der Beschwerde, während das Bundesverwaltungsgericht auf eine Vernehmlassung verzichtet.
F. Die II. öffentlich-rechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 30. Oktober 2009 an einer öffentlichen Sitzung beraten.

Erwägungen:
1. 1.1 Gegen Entscheide des Bundesverwaltungsgerichts auf dem Gebiet der Verrechnungssteuer ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht zulässig (Art. 82 lit. a in Verbindung mit Art. 83 sowie Art. 86 Abs. 1 lit. a BGG). Die Beschwerdeführer sind gestützt auf <ref-law> zur Beschwerde in öffentlich-rechtlichen Angelegenheiten legitimiert; auf die frist- und formgerecht eingereichte Beschwerde (Art. 100 Abs. 1 und Art. 42 BGG) ist daher einzutreten.
1.2 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht - inklusive Bundesverfassungsrecht -, Völkerrecht sowie kantonale verfassungsmässige Rechte (<ref-law>). Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (<ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. Umstritten ist im vorliegenden Verfahren, ob die Beschwerdeführer Anspruch auf Rückerstattung der Verrechnungssteuer von total Fr. 19'190'937.50 auf den im Jahre 2004 fällig gewordenen Teilliquidationsanteilen aus zwei Kapitalherabsetzungen der X._ Holding AG haben.
2.1 Der Bund erhebt gestützt auf <ref-law> eine Verrechnungssteuer u.a. auf dem Ertrag von beweglichem Kapitalvermögen (vgl. Art. 1 Abs. 1 des Bundesgesetzes vom 13. Oktober 1965 über die Verrechnungssteuer [VStG; SR 642.21]). Erwirbt eine Gesellschaft oder eine Genossenschaft gestützt auf einen Beschluss über die Herabsetzung des Kapitals oder im Hinblick auf eine Herabsetzung ihres Kapitals eigene Beteiligungsrechte (u.a. Aktien), so unterliegt die Differenz zwischen dem Erwerbspreis und dem einbezahlten Nennwert dieser Beteiligungsrechte der Verrechnungssteuer (<ref-law>). Diese Bestimmung gilt sinngemäss, wenn eine Gesellschaft oder Genossenschaft im Rahmen von Artikel 659 OR eigene Beteiligungsrechte erwirbt, ohne anschliessend ihr Kapital herabzusetzen, sofern die Gesellschaft oder Genossenschaft diese Beteiligungsrechte nicht innerhalb einer Frist von sechs Jahren wieder veräussert (Art. 4a Abs. 2 VstG).
Steuerpflichtig ist der Schuldner der steuerbaren Leistung (<ref-law>). Diese ist bei der Auszahlung, Überweisung, Gutschrift oder Verrechnung ohne Rücksicht auf die Person des Gläubigers um den Steuerbetrag zu kürzen (<ref-law>).
2.2 Die Verrechnungssteuer wird dem Empfänger der um die Steuer gekürzten Leistung nach Massgabe des Gesetzes vom Bund zurückerstattet (Art. 1 Abs. 2 in Verbindung mit <ref-law>). Im inländischen Verhältnis bezweckt die Verrechnungssteuer in erster Linie, die Deklaration der Erträge beweglichen Kapitalvermögens zu sichern; dem steuerehrlichen Inländer wird sie zurückerstattet (vgl. <ref-ruling> E. 4 S. 352 f. mit Hinweisen; MAJA BAUER-BALMELLI, Der Sicherungszweck der Verrechnungssteuer, 2000, S. 3).
Eine juristische Person hat Anspruch auf Rückerstattung der Verrechnungssteuer, wenn sie bei Fälligkeit der steuerbaren Leistung ihren Sitz im Inland hatte (<ref-law>), die mit der Verrechnungssteuer belasteten Einkünfte ordnungsgemäss als Ertrag verbucht hat (<ref-law> e contrario) und bei Fälligkeit der steuerbaren Leistung das Recht zur Nutzung des den steuerbaren Ertrag abwerfenden Vermögenswertes besass (<ref-law>). Der Antrag auf Rückerstattung muss innert drei Jahren nach Ablauf des Kalenderjahres, in dem die steuerbare Leistung fällig geworden ist, bei der Eidgenössischen Steuerverwaltung eingereicht werden (<ref-law> e contrario).
Die Rückerstattung der Verrechnungssteuer ist in allen Fällen unzulässig, in denen sie zu einer Steuerumgehung führen würde (<ref-law>).
2.3 Vorliegend wurde die Verrechnungssteuer von 35 % auf einem Teilliquidationsanteil von insgesamt Fr. 54'831'250.--, ausmachend Fr. 19'190'937.50, im Jahr 2004 von der X._ Holding AG als Schuldnerin der steuerbaren Leistung erhoben und ordnungsgemäss auf die Beschwerdeführer überwälzt. Diese stellten im Jahr 2005 ein Rückerstattungsbegehren, welchem vorerst stattgegeben wurde. Erst aufgrund einer Nachprüfung kam die ESTV zum Schluss, dass die Voraussetzungen für eine Rückerstattung der Verrechnungssteuer nicht erfüllt seien, weshalb sie am 8. Februar 2006 gestützt auf Art. 51 Abs. 2 und 3 VStG die Wiedereinzahlung der ihres Erachtens zu Unrecht gewährten Rückerstattungsbeiträge anordnete.
Da die erfolgte Rückerstattung der Verrechnungssteuer nicht auf einem förmlichen Entscheid nach <ref-law> beruhte, ist eine Rückforderung grundsätzlich möglich. Unbestritten ist, dass die formellen Voraussetzungen für eine Rückerstattung (rechtzeitiger und formgültiger Antrag) erfüllt sind. Weiter steht fest, dass die Beschwerdeführer bei Fälligkeit der steuerbaren Leistung ihren Sitz im Inland hatten und dass sie die mit der Verrechnungssteuer belasteten Einkünfte ordnungsgemäss als Ertrag verbucht hatten. Entgegen der Auffassung der ESTV kam die Vorinstanz auch zum Schluss, dass die Beschwerdeführer bei Fälligkeit der steuerbaren Leistung das Recht zur Nutzung an den 695'000 Inhaberaktien der X._ Holding im Sinne von <ref-law> besassen, was die ESTV nicht mehr in Frage stellt. Streitig ist damit im vorliegenden Fall nur noch, ob die Rückerstattung im Sinne von <ref-law> unzulässig war, weil sie zu einer Steuerumgehung führen würde.
2.4 Eine Steuerumgehung wird nach ständiger bundesgerichtlicher Rechtsprechung angenommen, wenn (a) eine von den Beteiligten gewählte Rechtsgestaltung als ungewöhnlich ("insolite"), sachwidrig oder absonderlich, jedenfalls den wirtschaftlichen Gegebenheiten völlig unangemessen erscheint, wenn zudem (b) anzunehmen ist, dass die gewählte Rechtsgestaltung missbräuchlich lediglich deshalb getroffen wurde, um Steuern einzusparen, die bei sachgemässer Ordnung der Verhältnisse geschuldet wären, und wenn (c) das gewählte Vorgehen tatsächlich zu einer erheblichen Steuerersparnis führen würde, sofern es von der Steuerbehörde hingenommen würde. Ob diese Voraussetzungen erfüllt sind, ist aufgrund der konkreten Umstände des Einzelfalls zu prüfen. Sind die Voraussetzungen der Steuerumgehung erfüllt, so ist der Besteuerung diejenige Rechtsgestaltung zugrunde zu legen, die sachgemäss gewesen wäre, um den erstrebten wirtschaftlichen Zweck zu erreichen (für die direkte Bundessteuer vgl. <ref-ruling> E. 5.2 S. 635 f.; Urteil 2A.135/2000 vom 9. November 2001 E. 6, in: ASA 72 S. 413; je mit Hinweisen; betreffend Rückerstattung der Verrechnungssteuer vgl. Urteil vom 11. Dezember 1981 E. 1b, in: ASA 50 S. 583 mit Hinweisen).
3. Die Beschwerdeführer rügen zunächst, der Sachverhalt sei in verschiedener Hinsicht offensichtlich falsch bzw. unvollständig und unter Verletzung der Untersuchungspflicht festgestellt worden. Sie bringen zahlreiche neue Tatsachen und Beweismittel vor, welche sie nicht früher hätten geltend machen können, weil erst ein noch nicht abgeschlossenes Strafverfahren gegen den ehemaligen CEO der Y._ Bank und gegen den ehemaligen Portfolio-Manager der Vorsorgewerke E._ - dank der Aufhebung des Bankgeheimnisses - kurz vor und nach Ergehen des angefochtenen Urteils Umstände zu Tage gebracht habe, welche die Beschwerdeführer entlasteten. Im Wesentlichen handelt es sich dabei um die Identität der offenbar mehrheitlich inländischen Verkäufer von Aktien an die Y._ Bank (vgl. lit. A.c und A.e hiervor).
Ob der Vorinstanz eine offensichtlich unrichtige oder unvollständige Sachverhaltsfeststellung (vgl. E. 1.2) vorgeworfen werden kann, wenn sie Umstände nicht berücksichtigte, die den Beteiligten im Urteilszeitpunkt noch gar nicht bekannt sein konnten, erscheint zumindest fraglich. Eher könnte allenfalls ein Revisionsgrund vorliegen (vgl. <ref-law> [SR 172.021]). Die Frage kann indes offen bleiben, weil die geltend gemachten neuen Sachumstände - wie aus dem Folgenden hervorgeht - ohnehin keinen Einfluss auf den Ausgang des Verfahrens hätten (vgl. <ref-law>).
4. 4.1 Die Vorinstanz führte im angefochtenen Entscheid aus, schon aufgrund der zeitlichen Abwicklung und der damit verbundenen Umstände ergebe sich, dass die von den Beteiligten gewählte Vorgehensweise ungewöhnlich sei. In einer Gesamtbetrachtung sei festzustellen, dass die Y._ Bank Aktien der X._ Holding, welche sie für deren vorgesehene Kapitalherabsetzung benötigte und die sie entweder bereits besass oder sich kurzfristig auf dem Markt beschaffte, an die Beschwerdeführer veräusserte, um sie kurz darauf von diesen wieder zurückzukaufen und anschliessend für die Kapitalherabsetzung zu verwenden. Diese Vorgehensweise mache aus Sicht der Y._ Bank und der X._ Holding wirtschaftlich keinen Sinn, und auch die Beschwerdeführer vermöchten nicht aufzuzeigen, welches die wirtschaftlichen Gründe für die Wahl dieser Vorgehensweise gewesen sein sollten.
Die Vorinstanz folgerte weiter, dass die Y._ Bank bzw. die X._ Holding mit dem von ihnen gewählten Vorgehen tatsächlich Steuern sparen könnten, wenn dieses akzeptiert würde. Diese rechtliche Situation sei auch für die Beschwerdeführer klar gewesen; diese hätten im Detail Kenntnis von der Gesamttransaktion gehabt und damit an der Steuerumgehung mitgewirkt.
4.2 Die Vorinstanz bezieht sich auf einen ähnlich gelagerten Fall, in welchem das Bundesgericht auf eine Steuerumgehung geschlossen hat (Urteil 2A.660/2006 vom 8. Juni 2007, in: RDAF 2008 II S. 536). Damals wollte eine Aktiengesellschaft eine Kapitalherabsetzung durchführen. Die dafür vorgesehenen 20'000 Aktien hatte sie bereits erworben, ohne den Veräusserern die Verrechnungssteuer belastet zu haben. Nach Beratung durch eine Bank verkaufte sie dieser 20'000 Aktien, um sie nach kurzer Zeit zwecks Kapitalherabsetzung wieder zurückzuerwerben. Dabei belastete sie der Bank die Verrechnungssteuer, welche diese in der Folge bei der ESTV zurückverlangte und (zunächst) auch erhielt. Das Bundesgericht beurteilte dieses Vorgehen als Steuerumgehung unter Mitwirkung und in Kenntnis des Empfängers und zugleich Beraters und verweigerte der Bank die Rückerstattung der Verrechnungssteuer (zur Kritik an diesem Urteil vgl. E. 4.4 hiernach).
4.2.1 Dieser von der Vorinstanz herangezogene Fall unterscheidet sich aber sachverhaltsmässig wesentlich vom hier zu beurteilenden: Die Beschwerdeführer haben auf entsprechende Anfrage der Y._ Bank im Januar 2004 die gewünschten Aktien aus ihren bereits vorhandenen Beständen angedient. Sie taten dies unter der Bedingung, eine gleiche Menge der Aktien wieder erwerben zu können, weil sie diese Investition, welche durch die Herabsetzung der Aktienkapitals noch werthaltiger wurde, behalten wollten. Daraufhin verkaufte die Y._ Bank den Beschwerdeführern zunächst am 12. Januar 2004 195'000 Aktien der X._ Holding, um von ihnen am 20. Januar 2004 die 195'000 zur Herabsetzung benötigten Aktien zu erwerben. Die Y._ Bank rechnete die Verrechnungssteuer ab, welche die Beschwerdeführer bei der ESTV zurückverlangten und (zunächst) auch erhielten. Das gleiche Vorgehen wiederholte sich im Juli 2004 mit 500'000 X._ Holding Aktien. Die Y._ Bank hatte als "Market Makerin" bzw. Blockhändlerin einen Stock solcher Aktien vorrätig oder beschaffte sich diese gemäss den Feststellungen der Vorinstanz (angefochtenes Urteil E. 6.4.2) jeweils kurzfristig auf dem Markt. Weitergehend haben die Beschwerdeführer an den Operationen um die Kapitalherabsetzungen soweit festgestellt nicht mitgewirkt.
4.2.2 Die Vorinstanz kommt mit der ESTV zum Schluss, die Vorgehensweise ("Hin und Her von zahlenmässig identischen Titeln" zwischen der Y._ Bank und den Beschwerdeführern) mache wirtschaftlich keinen Sinn; die Y._ Bank hätte zweckmässigerweise die von ihr erworbenen Aktien direkt der Muttergesellschaft (X._ Holding) zwecks Kapitalherabsetzung zur Verfügung stellen sollen, statt den Umweg über die Vorsorgewerke E._ zu gehen. Die gesamte Transaktion lasse sich nur mit dem Bestreben, die Verrechnungssteuer einzusparen, erklären, und die Beschwerdeführer hätten dabei mitgewirkt bzw. davon gewusst.
Gewiss bezweckte die X._ Holding mit dem Kauf der zur Herabsetzung benötigten Aktien, die Verrechnungssteuer einzusparen, weil die beauftragte Y._ Bank diese den Beschwerdeführern in Rechnung stellen konnte und die Beschwerdeführer rückerstattungsberechtigt waren. Ein solches Vorgehen ist allerdings üblich und erlaubt, jedenfalls keineswegs ungewöhnlich und sachwidrig im Sinne der Kriterien einer Steuerumgehung (vgl. dazu etwa PHILIPP LÜTOLF/ROGER M. KUNZ, Aktienrückkäufe in der Schweiz, in: Der Schweizer Treuhänder 2005, S. 280 ff., insbesondere S. 284 f.; GAUDENZ G. ZINDEL, Aktienrückkäufe und Kapitalherabsetzungen, in: Festschrift für Peter Forstmoser (...), 2003, S. 571 ff., insbesondere S. 577 ff.). Dies räumt denn auch die Vorinstanz ein, wenn sie ausführt, die Feststellung, es sei üblich und zulässig, dass sich eine rückkaufende Gesellschaft an rückerstattungsberechtigte Einzelaktionäre wende, möge zutreffen (angefochtenes Urteil E. 6.4.2). Gemäss der Vorinstanz besteht jedoch das zusätzliche Element, welches die Transaktionen ungewöhnlich mache, darin, dass die Y._ Bank den Beschwerdeführern bereits vorhandene oder kurz zuvor beschaffte Aktien verkauft habe, um sie umgehend wieder zurückzukaufen.
4.2.3 Dieser Erwägung der Vorinstanz kann nicht gefolgt werden: Nicht jeder Aktieninhaber ist bereit, einer Aktiengesellschaft seine Aktien zwecks Kapitalherabsetzung zu überlassen, schon nur, weil ihm in diesem Fall die Verrechnungssteuer auf der Differenz zwischen dem Verkaufspreis und dem einbezahlten Nennwert in Abzug gebracht wird und er deren Rückerstattung beantragen und abwarten muss. Es leuchtet deshalb durchaus ein, dass eine herabsetzungswillige Aktiengesellschaft einen Verkäufer sucht, der - wie hier die Beschwerdeführer - mit der Veräusserung der gewünschten Menge Wertpapiere unter Steuerabzug und -rückerstattung einverstanden ist. Es ist auch durchaus glaubhaft und nachvollziehbar, dass der zur Mitwirkung bereite Verkäufer nicht primär am mit dem Geschäft verbundenen Gewinn interessiert ist, sondern Ersatz für die angedienten Aktien verlangt, weil er seine Investition in die Aktiengesellschaft erhalten möchte. Es kann deshalb auch nicht als unüblich bezeichnet werden, dass die mit der Aktienbeschaffung betraute Bank für Ersatz sorgen und diesen dem Verkäufer zuhalten muss. Für die Ersatzpapiere spielt es dann keine Rolle, ob sie an der Börse erworben wurden oder von Verkäufern stammen, welche die Rückerstattung der Verrechnungssteuer nicht verlangen könnten. Derartigem kombiniertem Vorgehen liegt grundsätzlich eine erlaubte Steuerplanung und -einsparung (vgl. etwa Urteil 2A.11/1994 vom 16. August 1996 E. 5c, in: ASA 66 S. 406) zugrunde, welche für sich betrachtet bzw. wegen dem damit verbundenen "Hin und Her" noch nicht als ungewöhnlich im Sinne einer verpönten Steuerumgehung qualifiziert werden kann.
Dazu bedürfte es mehr, etwa - wie zum Beispiel im oben erwähnten Fall (Urteil 2A.660/2006 vom 8. Juni 2007) - dass der Veräusserer in Kenntnis der massgebenden Umstände nur zu deren Manipulation auftritt, um bereits zur Herabsetzung beschaffte Aktien, auf denen die Aktiengesellschaft die Verrechnungssteuer nicht überwälzen könnte und (aufgerechnet ins Hundert) selber tragen müsste, mit seinem Einverständnis und Mitwirken im Ergebnis von der Verrechnungssteuer zu befreien. Erst solche unüblichen Dispositionen können als ungewöhnlich im Sinne einer Steuerumgehung bezeichnet werden, nicht aber bereits das hier festgestellte Vorgehen eines Aktienkaufs von einem Rückerstattungsberechtigten mit gleichzeitiger Ersatzbeschaffung auf seinen ausdrücklichen Wunsch hin. Insbesondere ist vorliegend nicht erstellt, dass die X._ Holding im Zeitpunkt, als sie die Kapitalherabsetzung beschloss, bereits über genügend grosse Bestände eigener Aktien verfügte, die sie für diesen Zweck verwenden konnte und wollte, aber zuerst (wie im Urteil 2A.660/2006 vom 8. Juni 2007) zwecks "Befreiung von der Verrechnungssteuer" noch einmal in Umlauf setzen, d.h. an die Beschwerdeführer verkaufen und zurückerwerben, musste. Umso weniger kann den Beschwerdeführern ein entsprechendes Mitwissen unterstellt werden. Erst ein solches oder auf vergleichbaren Machenschaften beruhendes Vorgehen würde auf eine Steuerumgehung hindeuten.
4.2.4 Im Weiteren kann auch nicht gesagt werden, die Beschwerdeführer hätten nur zum Schein mitgewirkt bzw. einfach die erworbenen Aktien umgehend wieder zurückverkauft, was ein wesentliches Indiz für die Annahme einer Steuerumgehung wäre. Sie verfügten nach den - für das Bundesgericht verbindlichen - Feststellungen der Vorinstanz allesamt über genügend grosse Bestände an Inhaberaktien der X._ Holding, um die zur Kapitalherabsetzung überlassenen Aktien auch ohne Ersatz andienen zu können.
4.2.5 Gewiss steht nicht mit Sicherheit fest, dass seitens der X._ Holdingund der für sie tätig gewordenen Y._ Bank keine weiteren Vorkehren getroffen worden sind, welche die Geschäftsabwicklung gesamthaft betrachtet doch als Steuerumgehung erscheinen lassen würden. Diesbezügliche Feststellungen fehlen aber im - für das Bundesgericht verbindlich - vorinstanzlich festgestellten Sachverhalt. Die Beweislast für das Vorliegen der steuerbegründenden Elemente einer Steuerumgehung liegt bei den Steuerbehörden (vgl. <ref-ruling> E. 3c/aa S. 284 mit Hinweisen). Bei dieser Sachlage kann den Beschwerdeführern nicht vorgeworfen werden, sie hätten an einer Steuerumgehung durch die X._ Holdingmitgewirkt. Ihre Kenntnis und Mitwirkung ist auf Handlungen beschränkt geblieben, die in ihrer Gesamtheit noch nicht als ungewöhnliche, sachwidrige oder absonderliche Rechtsgestaltung im Sinne der Kriterien für die Annahme einer Steuerumgehung (vgl. E. 2.4) bezeichnet werden können. Die Beschwerdeführer haben davon ausgehen dürfen, das Vorgehen der X._ Holdingsei auf das erlaubte Vermeiden einer Steuer ausgerichtet, an dem sie trotz der mit der Verrechnungssteuer verbundenen Formalitäten und der zeitweiligen Blockade von beträchtlichen Mitteln unbeschadet mitwirken und interessiert sein durften, zumal sie den Aktienbestand halten konnten, dieser an Werthaltigkeit noch zunahm und die Transaktion mit einem gewissen Gewinn verbunden war.
4.3 Dazu kommt, dass die Verrechnungssteuer im Wesentlichen eine Sicherungssteuer und damit nicht in erster Linie auf fiskalische Erträge ausgerichtet ist (vgl. <ref-ruling> E. 4 S. 352 f.; Urteil 2A.660/2006 vom 8. Juni 2007 E. 3.2; BAUER-BALMELLI, a.a.O., S. 3 und 212 ff.). Ist wie im vorliegenden Fall der Sicherungszweck soweit absehbar erreicht worden, so kann nicht leichthin auf eine Steuerumgehung geschlossen und das Sicherungssubstrat einbehalten werden.
4.4 Das hiervor mehrfach zitierte Urteil 2A.660/2006 vom 8. Juni 2007 wurde in der Literatur teilweise kritisiert (vgl. etwa URS BEHNISCH/ANDREA OPEL, Die steuerrechtliche Rechtsprechung des Bundesgerichts im Jahre 2008, ZBJV 145/2009 S. 565 ff.; PETER GURTNER, Stempelabgaben und Verrechnungssteuer, ASA 78 S. 41 ff.): Wenn von einer Steuerumgehung der Bank ausgegangen werde, sei es nicht nachvollziehbar, weshalb das Bundesgericht der Besteuerung nicht jene Rechtsgestaltung zugrunde gelegt habe, die aus Sicht der Aktiengesellschaft sachgemäss gewesen wäre, um den erstrebten wirtschaftlichen Zweck zu erreichen. Eine Steuerumgehung wäre damit ausschliesslich auf Stufe Steuererhebung (bei der Aktiengesellschaft) und nicht zusätzlich auch noch auf jener der Rückerstattung (bei der Bank) zu bejahen. Indem das Bundesgericht der Bank die Rückerstattung der Verrechnungssteuer verweigere, werde neu die Rechtsfigur der Mitwirkung bei einer Steuerumgehung geschaffen und damit steuerlich nicht jener Steuerpflichtige gestraft, der eine Steuerumgehung begangen habe, sondern der Mitwirkende.
Die dargestellte Kritik erscheint nicht als von vornherein verfehlt. Für den vorliegenden Fall kann indessen die Frage offen gelassen werden, ob die Steuerumgehung ausschliesslich auf Stufe Steuererhebung (hier bei der X._ Holding) und nicht zusätzlich auch noch auf Stufe Rückerstattung (hier bei den Vorsorgewerken E._) zu bejahen wäre: Die ESTV hat nur auf die Vorsorgewerke E._ zurückgegriffen, welche - wie hiervor unter E. 4.2.1 bis 4.2.5 ausführlich dargelegt - keine Steuerumgehung begangen haben. Die Frage, ob auf Seiten der X._ Holding eine Steuerumgehung zu bejahen wäre, bildete nicht Gegenstand des vorliegenden Verfahrens und braucht daher nicht näher untersucht zu werden.
5. Zusammengefasst ergibt sich, dass die Kriterien für die Annahme einer Steuerumgehung durch die Beschwerdeführer vorliegend nicht erfüllt sind; diese haben demzufolge Anspruch auf Rückerstattung der von der ESTV zurückverlangten Verrechnungssteuer in der Höhe von Fr. 19'190'937.50. Die Beschwerdeführer beantragen neben der Rückerstattung einen Vergütungszins ab 28. Juni 2006 von 5 %. Praxisgemäss - und von der ESTV beim vorliegenden Verfahrensausgang nicht bestritten - ist dieser Betrag (in Analogie zu <ref-law> in Verbindung mit Art. 1 Abs. 1 der Verordnung vom 29. November 1996 über die Verzinsung ausstehender Verrechnungssteuern [SR 642.212]) ab dem Datum der Rückzahlung durch die Beschwerdeführer an die ESTV mit 5 % zu verzinsen (Urteil vom 25. November 1983, in: ASA 53 S. 95).
6. 6.1 Daraus ergibt sich, dass die Beschwerde gutzuheissen und das Urteil des Bundesverwaltungsgerichts vom 5. November 2008 aufzuheben ist. Die ESTV ist anzuweisen, den Beschwerdeführern die Verrechnungssteuer von insgesamt Fr. 19'190'937.50, zuzüglich eines Zinses von 5 % ab 28. Juni 2006, zurückzuerstatten.
6.2 Dem Ausgang des Verfahrens entsprechend hat die ESTV, um deren Vermögensinteresse es sich vorliegend handelt, die bundesgerichtlichen Kosten zu bezahlen (Art. 66 Abs. 1 und 4 BGG). Zudem wird die ESTV verpflichtet, den Beschwerdeführern eine Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Zur Bestimmung der Kosten- und Entschädigungsfolgen des Verfahrens vor dem Bundesverwaltungsgericht wird die Sache an die Vorinstanz zurückgewiesen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, und das Urteil des Bundesverwaltungsgerichts vom 5. November 2008 wird aufgehoben.
2. Die Eidgenössische Steuerverwaltung wird angewiesen, den Beschwerdeführern die Verrechnungssteuer von insgesamt Fr. 19'190'937.50, zuzüglich eines Zinses von 5 % ab 28. Juni 2006, wie folgt zurückzuerstatten:
dem Wohlfahrtsfonds A._: Fr. 843'937.50;
der Stiftung B._: Fr. 269'500.--;
der Stiftung C._: Fr. 1'640'625.--;
dem Wohlfahrtsfonds D._: Fr. 404'250.--;
der Pensionskasse E._: Fr. 16'032'625.--.
3. Die Angelegenheit wird zu neuem Entscheid über die Kosten und Parteientschädigung für das vorinstanzliche Verfahren an das Bundesverwaltungsgericht zurückgewiesen.
4. Die Gerichtskosten von Fr. 40'000.-- werden der Eidgenössischen Steuerverwaltung auferlegt.
5. Die Eidgenössische Steuerverwaltung hat die Beschwerdeführer als Solidargläubiger für das bundesgerichtliche Verfahren mit insgesamt Fr. 50'000.-- zu entschädigen.
6. Dieses Urteil wird den Beschwerdeführern, der Eidgenössischen Steuerverwaltung sowie dem Bundesverwaltungsgericht schriftlich mitgeteilt.
Lausanne, 30. Oktober 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger