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.
you can pay hotel with cash if you want to stay anonymous you don't reach anonymity with BTC alone. hotels will ask for ID