http://cointelegraph.com/news/112394/lithuanian-airline-air-lituanica-gets-its-first-customer-using-bitcoinAir Lituanica is an airline based in Lithuania, which operates scheduled flights in Europe to various destinations such as Paris, Amsterdam, Prague and Berlin.
The airline's payment options include e-bank, credit card, bank transfer (as long as you're not based in Vietnam I guess), and since couple of days, Bitcoin. Both payments via e-bank and credit card require extra fees, respectively 5 LTL (~ 1.9 USD) and 75 LTL (~28.5 USD) per transaction, while bank transfers and Bitcoin don't cost any fee.