Expedia allows Bitcoin payment for hotel bookings. Expect them to add flight bookings soon too, though I don't see much benefit in that. Hotel booking I can understand if one is looking for some anonymity.