For example, say a company promises that by using their product, you'll save $500 per month, for an initial investment of $5,000. Only take them up if they're willing to front the initial cost and pay themselves back with the savings, or at the very least guarantee the savings.
This will quickly show you how much confidence the vender hasin their claims of savings.
HotelSaver's pricing model screams, "We're not confident we can offer you any savings."
If you're not confident enough in your skills or business model to risk $20 worth of effort on my behalf, why should I be confident enough to risk $20 on your skills and business model?
My guess is that there's a wide variation in available savings, depending on things like how far in advance the hotel is booked, where it's booked, what hotel/chain the booking is at. While you might need some manual effort to find the best deal possible, I'll bet you could filter out "good" vs. "bad" prospects pretty quickly in a completely automated manner.
For example, someone submits a reservation that's 40% below average rates for a stay in a week, at a hotel that doesn't typically price match? It should be possible to develop an automated system that says, "Sorry, we can't offer any savings on this reservation." Your staff doesn't spend any time, and your customer doesn't spend any money.
Someone on the other hand submits a reservation at 10% above average rates at a hotel in 4 months? You can fairly safely take that bet and save them some money.
Find a pricing model that lets you do this. Maybe it's a percentage of the savings, maybe a flat-fee that's refunded if you can't save them more than the fee. Maybe it's something else. Either way, you need to show your customers that you're confident in your ability to save them money.
Another great service would be automated re-booking. Partner with a service like FancyHands, so that you can call and request price-matches/adjustments for your customers. For people like me that hate picking up the phone, it'd be a huge benefit. It would also let you verify/confirm the savings.