Sachverhalt: A. Am 5. Juni 2003 stellte die Y._ Limited mit Sitz auf Bermuda bei der Eidgenössischen Steuerverwaltung einen Antrag auf Vergütung der Mehrwertsteuer im Betrag von Fr. 116'627.54 auf den Leistungen, die an sie im Jahre 2002 im Inland ausgeführt wurden (vgl. Art. 90 Abs. 2 lit. b des Bundesgesetzes über die Mehrwertsteuer vom 2. September 1999, MWSTG, SR 641.20). Am 17. Januar 2004 stellte sie auch einen Antrag auf Vergütung der Mehrwertsteuer im Betrag von Fr. 565'830.39 für das Jahr 2003. Mit Entscheid vom 27. Februar 2004 wies die Eidgenössische Steuerverwaltung die Vergütungsanträge ab, da die Antragstellerin weder ihre Unternehmereigenschaft noch die Art der Verwendung der bezogenen Leistungen nachgewiesen hatte. Im Einspracheverfahren hiess die Eidgenössische Steuerverwaltung mit Entscheid vom 18. Mai 2006 den Antrag der Y._ Limited auf Vergütung der Mehrwertsteuer im Betrag von Fr. 116'627.54 und Fr. 565'830.39 aufgrund der neu eingereichten Unterlagen gut. Einen Vergütungszins richtete die Verwaltung indessen nicht aus, da Bermuda kein entsprechendes Gegenrecht gewähre. Auch sprach sie keine Parteientschädigung zu. B. Mit Beschwerde vom 14. Juni 2006 beantragt die Y._ Limited der Eidgenössischen Steuerrekurskommission, es sei der Einspracheentscheid der Eidgenössischen Steuerverwaltung aufzuheben, soweit er ihr keinen Vergütungszins und keine Parteientschädigung zuspreche (Ziffern 3 und 5 des Einspracheentscheides). Es sei ihr ein Verspätungszins von 5 % per annum auf Fr. 116'627.54 für die Zeit vom 5. August 2003 bis 30. Mai 2006 und auf Fr. 565'831.00 für die Zeit vom 21. März 2004 bis 30. Mai 2006 zu bezahlen. Sodann sei ihr für das Einspracheverfahren eine Parteientschädigung zuzusprechen. Das Bundesverwaltungsgericht, welches das Verfahren von der Eidgenössischen Steuerrekurskommission übernommen hatte, hiess mit Urteil vom 29. April 2008 die Beschwerde im Sinne der Erwägungen teilweise gut. Es wies die Sache zur Berechnung des geschuldeten Vergütungszinses ab dem 61. Tag seit Gesuchstellung bis zur Zahlung der Steuervergütung an die Eidgenössische Steuerverwaltung zurück. Dem Antrag auf Zusprechung einer Parteientschädigung für das Einspracheverfahren gab das Bundesverwaltungsgericht nicht statt. Die Verfahrenskosten im Betrag von Fr. 2'000.-- auferlegte es mit Fr. 200.-- der teilweise obsiegenden Y._ Limited und sprach ihr eine reduzierte Parteientschädigung zu. Der Vorinstanz wurden keine Kosten auferlegt. C. Hiergegen führt die Eidgenössische Steuerverwaltung Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das Urteil des Bundesverwaltungsgerichts vom 29. April 2008 sei aufzuheben, soweit es nicht die Parteikostenentschädigung im Einspracheverfahren betreffe (vgl. angefochtenes Urteil E. 4), und der Einspracheentscheid vom 18. Mai 2006 sei zu bestätigen. Die Y._ Limited schliesst auf Abweisung der Beschwerde. Das Bundesverwaltungsgericht verzichtete auf eine Vernehmlassung. 