There was once a wiki for such things, but now I'm having some trouble finding it.

With Gyft you can buy Marriott gift cards with Bitcoins which can be used at any hotel under the Marriott (), but I don't know if those are usable at any Marriott branded property:
 - http://www.marriott.com/marriott-brands.mi

For AirBNB-type of rentals there is 9Flats, which accepts bitcoin:
 - http://9Flats.com

Otherwise, you can use a travel operator that accepts Bitcoin:
 - http://www.turismonordico.com
 - http://en.bitcoin.it/wiki/Trade#Travel_Companies

If you are from the U.S., then anyone can move value from Bitcoins to a Priceline.com gift e-card, or Booking.com, or Radisson, Accor brands, and many others using Lyoness. (transfer USDs to Dwolla through Camp BX then Dwolla to Lyoness):
 - http://bitcointalk.org/index.php?topic=156968.msg1664676#msg1664676