Yeah, Expedia removed the option to pay with Bitcoin as far as I"'m aware of.
Tried booking a vacation last year with them and couldn't find the option any more.
Aside from the services other people have mentioned here, there's also
https://btctrip.com/Seems like this is just for flights, but they offer pretty cheap rates.
https://destinia.co.uk/m/bitcoins allows you to book hotels with Bitcoin.