Our solution was basically brand loyalty -- the Motel 6 people published a book with addresses and phone numbers of all their motels in the US. The scheme is, you get on the road, and some time around 7pm, you stop for dinner, and make a reservation (from the payphone) at the Motel 6 that's about 100 miles ahead, and off you go.
The only time it didn't work well was one time when there was a large event in Cheyenne, Wyoming (I think it was the world square-dancing championship, but my memory is uncertain), and we couldn't get a room for love or money. We pushed on to Laramie, which was a little dangerous given how long we'd been at it, but it worked out OK.