>  Lines = deadweight loss, and deadweight loss = room for improvement.

Do you mean deadweight loss for the grocery store, or for the customer? Relatedly, does the grocery store care about deadweight loss for the customer?

If every grocery store in town has the same expected line length, then the entire cost of line length is borne by the consumer---since the line lengths are in equilibrium, none of the stores feel economic pressure to reduce their line length, and the line length is a fixed cost of food shopping (unless latency becomes comparable with the length of time a store is open during the day, in which case it's actually limiting the number of customers they can process per day, but I find this highly unlikely).

Granted, a store might try to differentiate itself by reducing its average line length, but there are many other (perhaps more important) factors that go into a consumer's choice regarding grocery stores, e.g., Wal-Mart mega-food-store competes on prices, Whole Foods competes on its customers' self-satisfaction (I kid, I love Whole Foods).

Intuitively, it feels like grocery store line length is in the noise when considering the decision process for most consumers, especially since I can get zero line length at almost any store by going during off-hours. If it's in the noise, there's no selection pressure to improve it.