Yes the PoW provier could get spammed. But the PoW provider has full flexibility on when (and for whom) to start mining.

For example, some could skip mining for "new and unproven" clients, with no reputation.

Others could only mine at higher difficulties for miners they've already had successful trades with, etc.

Still others could mine at a baseline "expensive" rate for new clients, but give cheaper rates to "trusted" clients they've mined for before, who they know will pay.

Lots of things possible :)