There are a lot of hidden assumptions here. For example I've assumed that people have enough information to make informed decisions about when to bail out. That means they have to know both the average frequency of new arrivals and the current line length. The conclusion that the go-to-the-front system is the best possible also requires everyone to be equally thirsty; otherwise we'd still get bad outcomes when less-thirsty newcomers displace their thirstier counterparts. If some are thirstier than others, the go-to-the-front system is inferior to a full-fledged market in line placement, but probably still superior to the go-to-the-back custom that pretty much everybody uses now.
The go-to-the-front system also requires an enforcement mechanism to prevent people from leaving the end of the line and re-entering at the beginning—just as the current system requires a mechanism to prevent people from cutting in. At the water fountain, social disapproval seems like a reasonably effective enforcement mechanism. For telephone queues, caller ID might work: If you hang up and call back, you're automatically disconnected.
So, here's my proposal to reform telephone customer service: An initial recording announces the average frequency of calls and explains that each new call will be placed in front of yours. Every minute or so, a new recording tells you how far back in line you've been pushed. If you hang up and call back, you can't get through. And for those with true emergencies (like the desperately thirsty customers at the water fountain), there can be a separate queue that you pay to join.
If that system strikes you as terrible, it's partly because you're not thinking about how much shorter the waiting time would be on average. Surely it's worth an experiment. I'm waiting for someone to try it.