Hate to be negative nellie but this strikes me as a very small niche that should almost disappear on its own. Which is fine, just not something I'd expect from YC or venture in general.
While getting "walked" is the short story, you could flatten this out to other overbooked rentals like automobiles. If you can set up a system that is efficient enough to allow a company to overbook without worrying about hurting customer satisfaction I imagine there is a lot of money to be made.