I've come up with a variant on dutch auctions which solves this problem quite beautifully. The restaurant continues to charge the same amounts it does currently, with the same menu, but there's a 'seating fee' for sitting down which might be charged if the restaurant sells out in advance. The amount of the seating fee is determined by when the restaurant becomes completely booked, with the fee going down the later the selling out happens, possibly going down to zero at the end. By making a reservation when the potential seating fee is a certain amount, a customer is declaring that they're willing to pay the seating fee for that time period if it is necessary, but they aren't penalized for making an early reservation unless it would have been necessary to do an early reservation to get a seat. By waiting to make a reservation until later, a customer is declaring that they are unwilling to pay a higher price, but also allowing for the possibility that the restaurant will become fully booked and they won't get a seat. One of the nice features of this system is that the reservation system is essentially unchanged, allowing for trivial support of reserving particular time slots and tables.
This system also works for concerts and other events which have the potential to sell out.
A decent dot com business model would be to make a web site which performs this service for restaurants, and does fulfillment of seating fees and keeps a fraction of the seating fees for itself as a way of getting paid by restaurants. Restaurants would probably be quite agreeable to that, since seating fees are essentially found money for them, and they'd be happy to let someone else have a fraction of it.