Okay, to answer my own confused question: This is not a problem.

Transactions without any dust outputs, but with larger and smaller fees are still relayed over the network. Clients see those transactions that make it into the blockchain and adjust the definition of dust accordingly.

There is no chicken and egg problem because, in order to down-adjust the definition of dust, a client does not need to see a transaction with dusty outputs make it into the block chain. They merely need to see a tx with lower-than-average fees accepted into the blockchain. The force is undisturbed, and the satoshis flow freely.