Sachverhalt: A. Die im Detailhandel tätige Coop Genossenschaft mit Sitz in Basel (nachfolgend: Coop) ist seit dem 1. Januar 2001 im Register für Mehrwertsteuerpflichtige bei der Eidgenössischen Steuerverwaltung eingetragen. In Folge einer im Jahre 2003 durchgeführten Kontrolle erhob die Eidgenössische Steuerverwaltung mit Ergänzungsabrechnungen vom 13. Mai 2004 (EA) folgende Mehrwertsteuern je zuzüglich Verzugszinsen ab mittlerem Verfall: a) 1. Quartal 2000 bis 4. Quartal 2000: Fr. _ (EA Nr. 114'670); b) 1. Quartal 2001 bis 3. Quartal 2003: Fr. _ (EA Nr. 114'671); c) 4. Quartal 2003: Fr. _ (EA Nr 114'672). Anlass für die Nachbesteuerung gab das von Coop im Jahr 2000 eingeführte Kundenbindungsprogramm SUPERCARD. Durch Vorweisen der SUPERCARD an der Kasse erhält der Kunde je nach Höhe seines Einkaufs SUPERCARD-Punkte gutgeschrieben, die er zu einem beliebigen Zeitpunkt gegen eine Ware oder Dienstleistung (Prämie) aus dem Prämienkatalog einlösen kann. Die Prämien werden den Kunden durch Drittparteien, vornehmlich die A._ AG, erbracht. Diese stellen der Coop die ausgehändigten Prämien der Coop zuzüglich Mehrwertsteuer in Rechnung. Die Eidgenössische Steuerverwaltung vertrat die Ansicht, dass es sich bei den Treueprämien um umsatzabhängige Geschenke handle, die aufgrund einer Vereinbarung abgegeben werden und Naturalrabatte darstellen. Da die Umsätze von Coop, für welche die Punkte vergeben werden, überwiegend dem reduzierten Steuersatz für Lebensmittel (2,3 resp. 2,4 %) unterliegen, während die durch die Firma A._ AG erbrachten Treueprämien überwiegend zum Normalsatz (7,5 resp. 7,6 %) steuerbar seien, "muss das steuerbare Entgelt der zum reduzierten Satz gelieferten Waren nachträglich auf die verschiedenen Steuersätze aufgeteilt werden". Die Coop Genossenschaft bestritt die Nachforderungen. Sie machte im Wesentlichen geltend, zwischen dem ursprünglichen Kauf des Kunden und der Prämieneinlösung gäbe es keinen Zusammenhang. Alternativ schlug sie vor, die Prämien als unentgeltliche Zuwendungen (Geschenke) an die Kunden zu behandeln, mit der Folge, dass darauf allenfalls die Eigenverbrauchssteuer geschuldet sei. Mit Entscheiden vom 7. Juni 2007 bestätigte die Eidgenössische Steuerverwaltung die oben genannten Nachforderungen. Die dagegen erhobenen Einsprachen wies die Eidgenössische Steuerverwaltung je mit Entscheid vom 18. August 2008 ab. B. Gegen die Einspracheentscheide führte die Coop je Beschwerde beim Bundesverwaltungsgericht, welches die Verfahren vereinigte. Mit Urteil vom 16. September 2009 hiess das Bundesverwaltungsgericht die Beschwerden gut und hob die Einspracheentscheide vom 18. August 2008 auf. Das Bundesverwaltungsgericht erachtete zwar die Nachforderungen der Eidgenössischen Steuerverwaltung materiellrechtlich als begründet (Urteil E. 3 und 4). Es fand jedoch, dass die Beschwerde aus Gründen des Vertrauensschutzes gleichwohl gutzuheissen sei. Es verwies auf ein früheres Verfahren, in welchem die Eidgenössische Steuerverwaltung mit rechtskräftigem Einspracheentscheid vom 31. Oktober 2001 auf Antrag der Coop verbindlich festgestellt habe, dass die im Rahmen des Kundenbindungsprogramms SUPERCARD abgegebenen Treueprämien Naturalrabatte darstellen und diese nicht zusätzlich zu versteuern seien (Urteil E. 5). C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt die Eidgenössische Steuerverwaltung dem Bundesgericht, es sei das Urteil des Bundesverwaltungsgerichts vom 16. September 2009 aufzuheben und die beiden Einspracheentscheide vom 18. August 2008 seien zu bestätigen. Coop schliesst auf Abweisung der Beschwerde. Das Bundesverwaltungsgericht nahm zur Frage der Höhe der im vorinstanzlichen Verfahren zugesprochenen Parteientschädigung Stellung und verzichtete im Übrigen auf Vernehmlassung. 