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.

Erwägungen:
1. 1.1 Am 1. Januar 2010 trat das Bundesgesetz über die Mehrwertsteuer vom 12. Juni 2009 (MWSTG; SR 641.20) in Kraft. Auf die vor diesem Datum eingetretenen Tatsachen und entstandenen Rechtsverhältnisse bleibt das bisherige Recht anwendbar (Art. 112 Abs. 1 und 2 MWSTG). Zur Anwendung gelangen somit in materieller Hinsicht noch das Mehrwertsteuergesetz vom 2. September 1999 (aMWSTG; AS 2000 1300), in Kraft seit 1. Januar 2001, resp. vor diesem Zeitpunkt (Steuerperioden 1. Quartal 2000 bis 4. Quartal 2000) die Verordnung über die Mehrwertsteuer vom 22. Juni 1994 (aMWSTV; AS 1994 1464). Das Verfahrensrecht, soweit hier relevant, hat nicht geändert.
1.2 Entscheide des Bundesverwaltungsgerichts in Anwendung der Mehrwertsteuer-Gesetzgebung können mit Beschwerde in öffentlich-rechtlichen Angelegenheiten angefochten werden (Art. 82 lit. a, Art. 86 Abs. 1 lit. a BGG). Das Beschwerderecht steht auch der Eidgenössischen Steuerverwaltung zu (Art. 89 Abs. 2 lit. a BGG in Verbindung mit Art. 45b Abs. 2 aMWSTGV [SR 641.201], Art. 5 und 17 der Organisationsverordnung für das Eidgenössische Finanzdepartement vom 11. Dezember 2000, SR 172.215.1). Auf die form- (Art. 42 BGG) und fristgerecht (Art. 100 Abs. 1 BGG) eingereichte Beschwerde ist einzutreten.
1.3 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann die Verletzung von Bundesrecht gerügt werden (Art. 95 lit. a BGG). Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2, Art. 106 Abs. 2 BGG), grundsätzlich nur die in seinem Verfahren geltend gemachten Rechtswidrigkeiten, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 2.2.1 S. 389 mit Hinweisen).
1.4 Thema der vorliegenden Beschwerde ist die Frage des Vertrauensschutzes. Die Vorinstanz hat zwar im angefochtenen Entscheid die Nachforderungen der Eidgenössischen Steuerverwaltung materiellrechtlich beurteilt und als begründet erachtet (Urteil E. 3 und 4). Sie hat aber aus Gründen des Vertrauensschutzes (Schutz des berechtigten Vertrauens in die von der Steuerverwaltung mit rechtskräftigem Entscheid vom 31. Oktober 2001 gegebene Zusicherung) die Beschwerde gutgeheissen und die Einspracheentscheide aufgehoben (E. 5). Das ist durch die Eidgenössische Steuerverwaltung vorliegend angefochten.
Die Überprüfungsbefugnis des Bundesgerichts ist dennoch nicht auf die Frage des Vertrauensschutzes beschränkt. Streitgegenstand (wie er durch den angefochtenen Entscheid und die Beschwerdebegehren festgelegt wird, <ref-ruling> E. 5) sind die Steuerforderungen. Obschon die Eidgenössische Steuerverwaltung in der Beschwerdebegründung die Besteuerungsfrage nicht mehr thematisiert, ist die Beschwerdegegnerin befugt, in ihrer Vernehmlassung Fragen aufzuwerfen, welche die Steuerforderungen betreffen. Damit erhebt sie keine Anschlussbeschwerde und erweitert den Streitgegenstand nicht (was unzulässig wäre, <ref-ruling> E. 2 S. 32), sondern verlangt lediglich die Bestätigung des angefochtenen Entscheids (Aufhebung der Einspracheentscheide und Verzicht auf zusätzliche Besteuerung) mit einer anderen Begründung, falls die Hauptbegründung der Vorinstanz (Vertrauensschutz) vor Bundesgericht nicht standhalten sollte. Das ist erlaubt, zumal das Bundesgericht das Recht von Amtes wegen anzuwenden hat. Die Beschwerdegegnerin ist somit nicht darauf beschränkt, sich nur mit den Rügen der Beschwerdeführerin auseinanderzusetzen, sondern sie kann ihrerseits dartun, dass trotz allfälliger Stichhaltigkeit der Vorbringen der Beschwerdeführerin der angefochtene Entscheid im Ergebnis richtig ist (vgl. dazu <ref-ruling> E. 6c S. 255).
Zu befinden ist daher vorab über die Frage des Vertrauensschutzes. Führt diese Prüfung zu einem vom vorinstanzlichen Befund abweichenden Ergebnis, ist auch die materielle Begründetheit der Steuerforderungen zu prüfen.
1.5 Der Sachverhalt gemäss dem angefochtenen Entscheid ist im Übrigen nicht bestritten und für das Bundesgericht verbindlich (Art. 97 Abs. 1, 105 Abs. 1 und 2 BGG).
2. Die Beschwerdeführerin macht geltend, dass die Vorinstanz keinen Anlass hatte, die Anwendung des aus dem Gutglaubensschutz abgeleiteten Vertrauensschutzes im vorliegenden Fall zu prüfen. Abgesehen davon scheitere die Berufung auf den Gutglaubensschutz vorliegend auch daran, dass keine genügende Vertrauensgrundlage bestehe.
2.1 Gemäss Art. 9 BV hat jede Person Anspruch darauf, von den staatlichen Organen ohne Willkür und nach Treu und Glauben behandelt zu werden. Der Grundsatz von Treu und Glauben verleiht einer Person u.a. Anspruch auf Schutz des berechtigten Vertrauens in eine selbst unrichtige Auskunft oder Zusicherung der Behörde. Vorausgesetzt ist, dass die Person, die sich auf Vertrauensschutz beruft, berechtigterweise auf diese Grundlage vertrauen durfte und gestützt darauf nachteilige Dispositionen getroffen hat, die sie nicht mehr rückgängig machen kann. Zudem darf seit der Auskunftserteilung die gesetzliche Ordnung keine Änderung erfahren haben (<ref-ruling> E. 6.1 mit Hinweisen). Schliesslich scheitert die Berufung auf Treu und Glauben auch dann, wenn ihr überwiegende öffentliche Interessen gegenüberstehen (<ref-ruling> E. 4.1 mit Hinweisen). Im Steuerrecht, das vom Grundsatz der Gesetzmässigkeit beherrscht wird, kommt eine vom Gesetz abweichende Behandlung gestützt auf das Vertrauensprinzip ohnehin nur in Betracht, wenn die Bedingungen klar und eindeutig erfüllt sind (Urteil 2A.564/1998 vom 3. August 2000 E. 6a in fine, in: ASA 70 S. 764; <ref-ruling> E. 6.1 in fine mit Hinweisen).
2.2 Bereits im Jahre 1999 gelangte die Beschwerdegegnerin an die Eidgenössische Steuerverwaltung, um abklären zu lassen, welche mehrwertsteuerlichen Folgen das neue Kundenbindungsprogramm SUPERCARD habe. In der Folge kam es zu einem Feststellungsverfahren. Mit Entscheid vom 7. Juli 2000 stellte die Eidgenössische Steuerverwaltung fest, dass die Beschwerdegegnerin die Umsätze aus Lieferungen und Dienstleistungen, die sie im Rahmen des Kundenbindungsprogramms SUPERCARD den Karteninhabern gegen Verrechnung ihres Punkteguthabens erbringe, zum entsprechenden Steuersatz zu versteuern habe. Hiergegen liess die Beschwerdegegnerin durch ihre damalige Vertreterin, Swiss VAT, Einsprache erheben mit den Anträgen:
1. Es sei der Entscheid der Eidgenössischen Steuerverwaltung vom 7. Juli 2000 aufzuheben und festzustellen, dass die Treueprämien, welche sie im Rahmen des Kundenbindungsprogramms SUPERCARD den Karteninhabern gegen Verrechnung von umsatzabhängigen SUPERCARD-Punkten abgibt, als Naturalrabatte zu qualifizieren sind und somit nicht zusätzlich der Mehrwertsteuer unterliegen.
2. Es sei festzustellen, dass die Abgabe von Treueprämien gegen Verrechnung von SUPERCARD-Punkten bei Coop nicht zu einer Vorsteuerkürzung führt.
2.3 Mit Einspracheentscheid vom 31. Oktober 2001 hiess die Eidgenössische Steuerverwaltung Ziffer 1 der Rechtsbegehren gut und stellte fest, "dass die von der Genossenschaft Coop im Rahmen des Kundenbindungsprogramms SUPERCARD den Karteninhabern gegen Verrechnung von umsatzabhängigen SUPERCARD-Punkten abgegebenen Treueprämien Naturalrabatte darstellen und nicht zusätzlich zu versteuern sind".
Zu Ziffer 2 der Begehren (Vorsteuerkürzung) traf die Beschwerdeführerin aber keine Feststellung. Weshalb dies nicht erfolgte, ist hier nicht mehr zu beurteilen. Fraglich ist einzig, ob die Beschwerdegegnerin dem Einspracheentscheid entnehmen durfte, "dass für die Prämienlieferung keine Steuer geschuldet sei, bzw. keine zusätzliche Steuer im Verhältnis zum ursprünglichen Kaufgeschäft" entstehe, wie die Vorinstanz im angefochtenen Entscheid (E. 5.4) angenommen hat.
2.4 Das ist zu verneinen. Im Einspracheentscheid vom 31. Oktober 2001 (Ziff. 1.2 S. 5) führte die Beschwerdeführerin zur Frage der Treueprämien ("Naturalrabatte") aus:
"Es handelt sich bei einem solchen Naturalrabatt nicht um eine Entgeltsminderung im Sinne von Ziff. 251 der Wegleitung 2001. Der Naturalrabatt ist jedoch bezüglich der Anwendung verschiedener Steuersätze von Bedeutung. Unterliegen die gleichzeitig abgegebenen Gegenstände unterschiedlichen Steuersätzen, hat eine Aufteilung auf die verschiedenen Steuersätze zu erfolgen. Dies gilt auch, wenn der Abnehmer Bons erhält, die ihn ohne zusätzliches Entgelt zum Bezug von bestimmten Produkten berechtigen ..."
Aus dieser Begründung konnte unschwer abgeleitet werden, dass die unterschiedlichen Steuersätze im Hinblick auf die abgegebenen Treueprämien für den Steuersatz relevant werden können. Für die Beschwerdegegnerin, die von einem Steuerexperten und Mehrwertsteuerspezialisten vertreten wurde, war das erkennbar. Die Formulierung im Dispositiv Ziffer 1 des Einspracheentscheids vom 31. Oktober 2001, wonach "die von der Genossenschaft Coop im Rahmen des Kundenbindungsprogramms SUPERCARD den Karteninhabern gegen Verrechnung von umsatzabhängigen SUPERCARD-Punkten abgegebenen Treueprämien Naturalrabatte darstellen und nicht zusätzlich zu versteuern sind", kann damit in guten Treuen nicht dahin gehend verstanden werden, dass die Abgabe der SUPERCARD-Punkte und der daraus fliessenden Treueprämie zu keiner zusätzlichen steuerbaren Leistung führt. Damit wird einzig die Versteuerung eines weiteren Umsatzes ausgeschlossen.
2.5 Mit einer Nachbesteuerung oder Korrektur aufgrund unterschiedlicher Steuersätze musste daher gerechnet werden. Es fehlt damit an einer Vertrauensgrundlage, auf die sich die Beschwerdegegnerin berufen könnte. Nach dem Grundsatz der Gesetzmässigkeit im Steuerrecht besteht kein Raum, der Beschwerdegegnerin ein berechtigtes Vertrauen auf absolute Steuerneutralität des SUPERCARD-Kundenbindungsprogramms zuzugestehen. Da der Einspracheentscheid vom 31. Oktober 2001 nach dem Gesagten nicht im Sinne der Beschwerdegegnerin interpretiert werden kann, hilft ihr auch die Berufung auf die Rechtskraft dieses Entscheides (res iudicata) nicht. Die Beschwerde ist in diesem Punkt begründet.
3. Zu prüfen bleiben die mit den beiden Einspracheentscheiden vom 18. August 2008 bestätigten Leistungsentscheide der Beschwerdeführerin.
3.1 Wie erwähnt erhalten Coop-Kunden bei Einkäufen in Coop-Geschäften SUPERCARD-Punkte, wenn sie eine solche Karte vorweisen. Die gutgeschriebenen Punkte berechtigen den Kunden zum Bezug von Waren oder Dienstleistungen (sog. Treueprämien). Diese Leistungen werden den Kunden im Auftrag der Beschwerdegegnerin durch die Firma A._ AG und allenfalls weitere Drittparteien geliefert. Die Fakturierung der ausgehändigten Prämien zuzüglich Mehrwertsteuer erfolgt durch die A._ AG direkt an die Beschwerdegegnerin. Dieser steht hierfür der Vorsteuerabzug zu.
Die Beschwerdeführerin geht in ihren Leistungsentscheiden davon aus, dass es sich bei der Abgabe der Treueprämien um Naturalrabatte handelt. Da die Treueprämien vorwiegend aus Gütern bestünden, die mehrheitlich der Mehrwertsteuer zum Satz von 7,5 % resp. 7,6 % unterliegen, während die zum Erwerb der SUPERCARD-Punkte erforderlichen Verkaufsumsätze vorwiegend zum reduzierten Satz von 2,3 % resp. 2,4 % (Lebensmittel) steuerbar seien, habe eine Aufteilung des Entgelts aus den Verkaufsumsätzen auf die verschiedenen Steuersatzkategorien zu erfolgen.
Demgegenüber vertritt die Beschwerdegegnerin die Ansicht, die hier in Frage stehenden Treueprämien stellten umsatzabhängige Geschenke dar, die aufgrund einer Vereinbarung abgegeben werden und aus diesem Grund als Naturalrabatte zu qualifizieren sind. Wirtschaftlich gesehen wolle die Beschwerdegegnerin die Treueprämien nicht verkaufen, sondern aus Werbungsgründen verschenken. Es fehle damit an einem Leistungsaustausch. Da es sich um unentgeltliche Zuwendungen handle, seien sie im Eigenverbrauch zu versteuern, sofern der Freibetrag für Geschenke überschritten werde (Art. 9 Abs. 1 aMWSTG, Art. 8 Abs. 1 aMWSTV).
3.2 Der Vorinstanz ist beizupflichten, dass von einem eigentlichen Rabatt (Naturalrabatt) nicht gesprochen werden kann. Rabatte, Skonti u. dgl. stellen Entgeltsminderungen dar, die gemäss Art. 44 Abs. 2 aMWSTG (bzw. Art. 35 Abs. 2 aMWSTV) vom vereinbarten Entgelt in Abzug gebracht werden können (s. auch Ziff. 251 der Wegleitung 2001 für Mehrwertsteuerpflichtige). Der Abzug setzt deshalb einen unmittelbaren Zusammenhang mit dem getätigten Umsatz voraus, der das steuerbare Entgelt auslöst (vgl. Camenzind/Honauer/Vallender, Handbuch zum Mehrwertsteuergesetz, 2. Aufl. 2003, Rz. 271 f., 1188 ff., 1433 ff.). Weder ist hier eine solche Abzugsmöglichkeit beim Entgelt gegeben, noch besteht ein solcher unmittelbarer Zusammenhang zwischen Verkaufsumsatz und Prämienbezug. Es geht bei der Prämie vielmehr um eine Mehrleistung (Mehrlieferung) bei gleichbleibendem Entgelt. Aus diesem Grund ist eine Entgeltsminderung im Sinne von Art. 44 Abs. 2 aMWSTG (Art. 35 Abs. 2 aMWSTV) ausgeschlossen.
Mehrwertsteuerrechtlich sind vorliegend allerdings zwei Umsätze auseinanderzuhalten. Beim ersten erwirbt der Coop-Kunde in einem Verkaufsgeschäft der Beschwerdegegnerin Waren und Artikel, vornehmlich Nahrungsmittel, die zum reduzierten Steuersatz abgerechnet werden. Hierfür erhält er gegen Vorweisen der SUPERCARD eine Anzahl SUPERCARD-Punkte gutgeschrieben. Beim zweiten, unter Umständen erst sehr viel später erfolgenden Umsatz handelt es sich um die Einlösung der SUPERCARD-Punkte durch Bezug der im Prämienkatalog aufgeführten Artikel. Diese sind vornehmlich zum Normalsatz abzurechnen. Da nicht im Voraus feststeht, ob und wann der Kunde die Punkte einlösen wird und ob er sie allenfalls verschenkt oder verfallen lässt, handelt es sich um einen zweiten selbständigen Umsatz, für den der Kaufpreis vorausbezahlt wird.
Der Einkauf in einer Coop-Filiale und der Leistungsbezug beim späteren Prämiengeschäft bilden somit zwei eigenständige mehrwertsteuerliche Vorgänge.
3.3 Die Abgabe der Prämien gegen Punkte kann offensichtlich auch nicht als Geschenk qualifiziert werden mit der Folge, dass die Regeln über den Eigenverbrauch anzuwenden wären (Art. 9 aMWSTG, Art. 8 MWSTV). Ein Eigenverbrauchstatbestand liegt schon deshalb nicht vor, weil ein mehrwertsteuerrechtlicher Leistungsaustausch stattfindet. Das Entgelt besteht aus dem Gegenwert der Prämienpunkte, die der Käufer durch seine Einkäufe bei Coop erworben und vorausbezahlt hat. Dass es sich um ein Entgelt handelt, bestätigt die Beschwerdegegnerin selbst mit der Feststellung, "dass die entsprechenden Aufwendungen in die Bemessung der Produktepreise einfliessen".
3.4 Es ist unbestritten, dass die Erstumsätze, nämlich die Verkaufsumsätze in den Detailhandelsgeschäften von Coop, steuerbar vornehmlich zum reduzierten Satz, durch die Beschwerdegegnerin mehrwertsteuerrechtlich korrekt abgerechnet wurden. Mit dem Warenerwerb beim Erstumsatz erfolgt auch die Bezahlung für die damit erhaltenen SUPERCARD-Punkte, gleichgültig ob der Kunde diese je einlöst oder nicht. Werden diese Punkte später eingelöst, so ist hierfür der Kaufpreis bereits vorausbezahlt. Abzurechnen ist über die Vorauszahlung sowohl bei Ist- wie auch bei Sollversteuerung in jedem Fall mit der Vereinnahmung des Entgelts (Art. 43 Abs. 1 lit. a Ziff. 3 und lit. b aMWSTG, Art. 34 lit. a Ziff. 1 aMWSTV). Für die quartalsweisen Abrechnungen der Beschwerdegegnerin über die Verkaufsumsätze spielt es daher keine Rolle, ob die SUPERCARD-Punkte eingelöst werden oder nicht.
Werden die Punkte eingelöst, ist indes zu unterscheiden: Sofern als Treueprämien Gegenstände oder Leistungen bezogen werden, die dem gleichen Steuersatz unterliegen wie die Erstumsätze, hat dies mehrwertsteuerlich keine weiteren Folgen, weil die Steuer auf der Vorauszahlung (Bemessungsgrundlage, Art. 33 aMWSTG, Art. 26 aMWSTV) bereits mit dem richtigen Steuersatz abgerechnet worden ist. Zeigt sich hingegen wie im vorliegenden Fall, dass die Einlösung der Punkte überwiegend für Gegenstände erfolgt, die zum Normalsatz versteuert werden müssen, während die Erstkäufe vornehmlich einem reduzierten Steuersatz unterliegen, so ist der Steuersatz nachträglich zu korrigieren.
3.5 Die Beschwerdeführerin nahm in den Ergänzungsabrechnungen die Steuersatzkorrektur in der Weise vor, dass sie die Verkaufsumsätze der Beschwerdegegnerin, für welche Punkte vergeben wurden, auf die einzelnen Steuersatzkategorien aufteilte. Sie zog hierfür die kalkulatorischen Verkaufspreise heran. Nach diesem Schlüssel nahm sie auch auf dem Einkaufswert der Prämien eine Aufteilung vor. Auf dem Anteil, der prozentual dem Anteil des zum reduzierten Satz besteuerten Verkaufsumsatzes entspricht, rechnete sie sodann die Steuersatzdifferenz (Normalsatz abzüglich reduzierter Satz) auf.
Diese Art der Berechnung ist nicht zu beanstanden. Damit wird die Bemessungsgrundlage (Art. 33 aMWSTG) nicht geändert oder gar erweitert. Es handelt sich beim nachbelasteten Betrag lediglich um denjenigen Teil der Steuer, der auf dem ursprünglichen Verkaufsumsatz prozentual geschuldet wäre, wenn Einkauf und Prämiengeschäft zeitlich und örtlich zusammengefallen wären, wenn also von Anfang an auf dem Prämienanteil der richtige Steuersatz angewendet worden wäre. Da das Prämiengeschäft separat und erst viel später abgewickelt wird, muss die Steuersatzdifferenz beim Bezug der Prämienleistung nachträglich erhoben werden. Es wird somit die Steuerforderung auf einem Teil der Bemessungsgrundlage anhand des korrigierten Steuersatzes neu berechnet. Das entspricht dem Gesetz, das die Abrechnung der Steuer zum richtigen Steuersatz vorschreibt (Art. 36 aMWSTG, Art. 27 aMWSTV).
Es wird offensichtlich auch kein zusätzlicher Umsatz besteuert, da die Prämienleistung bereits mit der Vorauszahlung besteuert worden ist und die Steuersatzdifferenz auf der gleichen Bemessungsgrundlage nacherhoben wird. Die Vorbringen der Beschwerdegegnerin, die Nachforderung beruhe nicht auf einer gesetzlichen Grundlage und es würden zusätzliche Umsätze besteuert, ist daher falsch.
Unbehelflich ist der Einwand, dass die Steuersatzberichtigung gegen das Selbstveranlagungsprinzip verstosse. Auch wenn der Argumentation der Beschwerdegegnerin, wonach "als Ausfluss des Selbstveranlagungsprinzips die steuerliche Konsequenz für den Steuerpflichtigen im Zeitpunkt der Transaktion klar sein müsse", gefolgt wird, ist ihr Schluss daraus nicht richtig. Die Transaktion ist nämlich erst abgeschlossen, wenn die SUPERCARD-Punkte eingelöst sind. In diesem Zeitpunkt ist für den Steuerpflichtigen die Situation auch insofern klar, dass ein allenfalls von der Vorauszahlung abweichender Steuersatz berichtigt werden muss.
3.6 Dass für die Berechnung der Steuersatzdifferenz der Einkaufswert der Prämien (Aufwand der Beschwerdegegnerin für die Prämienleistungen) herangezogen wird, ist im Übrigen sachlich richtig. Auch bei der Bemessung der Steuer vom Eigenverbrauch wird bei neuen Gegenständen auf den Einkaufswert abgestellt (Art. 34 Abs. 1 lit. a aMWSTG, Art. 26 Abs. 3 lit. a Ziff. 1 aMWSTV). Da der hier vorliegende Fall der Korrektur des Steuersatzes bei nachträglicher Mehrlieferung nicht ausdrücklich geregelt ist, muss sich die Praxis an Grundsätze halten, die das Gesetz für verwandte Tatbestände, hier über den Eigenverbrauch, aufstellt.
3.7 Die beiden Einspracheentscheide der Eidgenössischen Steuerverwaltung vom 18. August 2008 erweisen sich nach dem Gesagten als rechtmässig. Die Beschwerde ist gutzuheissen, das angefochtene Urteil ist aufzuheben und die beiden Einspracheentscheide der Eidgenössischen Steuerverwaltung vom 18. August 2008 sind zu bestätigen.
4. Dem Ausgang des Verfahrens entsprechend sind die Kosten der Beschwerdegegnerin aufzuerlegen (Art. 65, Art. 66 Abs. 1 BGG). Eine Parteientschädigung ist nicht geschuldet (Art. 68 Abs. 1 und 3 BGG). Die Vorinstanz wird über die Kosten- und Entschädigungsfolgen ihres Entscheids neu zu befinden haben.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, der angefochtene Entscheid wird aufgehoben und die beiden Einspracheentscheide der Eidgenössischen Steuerverwaltung vom 18. August 2008 werden bestätigt.
2. Das Bundesverwaltungsgericht hat über die Kosten und Entschädigungsfolgen des vorinstanzlichen Verfahrens neu zu befinden.
3. Die Kosten des bundesgerichtlichen Verfahrens von Fr. 11'000.-- werden der Beschwerdegegnerin auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Bundesverwaltungsgericht, Abteilung I, schriftlich mitgeteilt.
Lausanne, 4. Mai 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Wyssmann