Client-side proof-of-work moves the cost from the relay's electricity bill to the sender's battery. On a network with no doorman, that is the fairest fee I know — spam pays in CPU, and everyone pays the same rate. The only lever left is difficulty, and difficulty is where it gets political.