Instead of prioritizing transactions based on PoW difficulty, which has the downside that a spammer generates high difficulty PoW by chance and competes vs regular users increasing their PoWs deliberately, we could prioritize not on difficulty itself, but by amount of PoWs, so that high difficulty PoWs done by chance don't skip to the top of the line.
Specific suggestion:

The PoW field on the blocks become an object that can contain up to 5 different ordered PoWs. For a block to be valid it only needs the first PoW to be valid. The rest are used only for prioritization and do not get added to the DB.

The first PoW is the same as today. Based on the previous (or height) field. The second PoW is based on the previous + the first PoW. The third PoW is based on the previous + 2nd PoW. And so on until the 5th poW.

Blocks are ordered based on how many PoWs they have in them, not their individual difficulty. This prevents individual lucky high difficulty PoWs being prioritized by chance.
In order to maximize costs for a spammer to affect regular users, the difficulty of every single PoW could be different.
So the first PoW is based on ledger bloat costs. The second is 2x the first. The 3rd difficulty is 5x the difficulty of the first. The 4th is 10x times and the 5th is 20x.
Advantages:

In this system, a 2 PoW block always takes priority over a 1 PoW block, a 3 PoW block always take precedent over a 2 PoW block. During the recent spam, it was suggested to increase PoW difficulty to 20x to actually skip the queue over the spammer given his high difficulty blocks done by chance.

After a block is cemented, you can discard the extra PoWs and keep only the first one in the DB, so the DB remains the same size.

This also permits a user to update his PoW live. Imagine during saturation a user send a 1 PoW block. They can now compute a second PoW and broadcast again, skipping the line.
Disadvantages:

The blocks can become bigger. A block with 5 poWs is obviously bigger than a block with a single PoW, although the difference is not particularly relevant I believe. But it is an increase in bandwidth during a moment where bandwidth is being used at it's highest (saturation).

More PoW checks. But that's the point of the first PoW. It still serves the same purpose of gatekeeper of the node resources. But still, more checks in a moment where resources are being used to the limit (saturation).
Update based on PlasmaPower Feedback
Plasma made a suggestion that is equivalent with less work. The first byte of the PoW field is choosen by the user to indicate the PoW level he is doing.
So transactions are ordered by the first byte of the PoW field, with each increasing number indicating a harder difficulty.
So a PoW with a low first byte would never be considered a high difficulty PoW, even if by chance it actually has a high difficulty.