Sachverhalt: A. Die X._ AG, damals mit Sitz in A._/ZH, heute in B._/ZH, bezweckt statutengemäss den Betrieb eines gewerbsmässigen Taxiflug-Unternehmens, das gewerbsmässige Ein- und Verchartern sowie das Halten und den Vertrieb von Flugzeugen. Die Gesellschaft verfügt über ein "Air Operator Certificate" (AOC) und ist seit dem Jahr 1988 im Besitz einer Betriebsbewilligung des Bundesamtes für Zivilluftfahrt zur Beförderung von Personen und Gütern im Nichtlinienverkehr ("Bedarfsluftverkehr"). Gemäss Luftfahrzeugregister war die X._ AG in den hier interessierenden Jahren 2001 bis 2007 die "Haupthalterin" der Flugzeuge HB-S._ (Falcon 2000EX) und HB-T._ (Falcon 900EX). Als deren "Haupteigentümer" wies das Luftfahrzeugregister im ersten Fall die Y._ SA aus, im andern Fall die ebenfalls in der Schweiz ansässige, nunmehr aber liquidierte Z._ AG. B. Zwischen der X._ AG und den beiden Eigentümergesellschaften bestanden verschiedene Verträge, die sich im Wesentlichen aus einer Leasing- und einer Operation-Komponente zusammensetzten. 70 bis 80 Prozent des Umsatzes erzielte die X._ AG ab dem Jahr 2006 mit der Beförderung von Personen, die weder ihr noch den Eigentümergesellschaften nahe stehen. Die Umsätze aus internationalen Flügen überwogen jene aus dem Binnenluftverkehr. C. Mit Verfügung vom 20. Mai 2010 verpflichtete die Eidgenössische Zollverwaltung, Zollkreisdirektion Schaffhausen, die X._ AG zur nachträglichen Bezahlung einer Einfuhrumsatzsteuer in Höhe von Fr. 71'769.50. Anlass bildeten Wartungsarbeiten an den Flugzeugen im Betrag von Fr. 944'335.--, welche die X._ AG im Zollausland hatte vornehmen lassen und von denen die Eidgenössische Zollverwaltung ausging, sie unterlägen der Einfuhrumsatzsteuer. Die gegen die Verfügung gerichtete Beschwerde wies die Eidgenössische Zollverwaltung, Oberzolldirektion, mit Beschwerdeentscheid vom 21. Oktober 2010 ab. Dagegen wandte sich die X._ AG an das Bundesverwaltungsgericht, das die Beschwerde am 1. November 2011 guthiess (Urteil A-8136/2010). D. Mit Eingabe vom 2. Dezember 2011 erhebt die Eidgenössische Zollverwaltung, Oberzolldirektion, beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragt, das angefochtene Urteil vom 1. November 2011 sei aufzuheben und der Beschwerdeentscheid der Oberzolldirektion vom 21. Oktober 2010 sei zu bestätigen. Während die Vorinstanz auf eine Vernehmlassung verzichtet, äussert sich die X._ AG (hiernach: die Steuerpflichtige) ausführlich und beantragt die Abweisung der Beschwerde. Dazu bezieht die Eidgenössische Zollverwaltung Stellung, was die Steuerpflichtige zu einer weiteren Stellungnahme veranlasst. Zu den auf Anordnung des Bundesgerichts nachgereichten Unterlagen der Eidgenössischen Zollverwaltung nimmt die Steuerpflichtige Stellung, wozu sich die Eidgenössische Zollverwaltung abschliessend vernehmen lässt. 