Here's a method of fixing block withholding attacks with a soft fork:

We require blocks to choose an arbitrary target, e.g. two bytes. We redefine the block PoW target to be "less than the difficulty, with the last two bytes being the target".

We require blocks to include a blinded hash of the target plus some junk (which blinds it) in the coinbase. The miner cannot arbitrarily switch targets.

The miner can now send the block header to hashers. Hashers do not know the target, and hence must submit all shares that matches the first PoW criteria (below difficulty) and delegate secondary verification to the miner. With two bytes as the target, there are 65335 false positives for every valid block.

Finally, we require miners to communicate a proof of their target hash (ie, the junk they generated) in a non-hashed area of the block. This can be a protocol extension. The target is already included in the hash as the last two bytes.

This can be deployed as a soft fork with miner opt in, triggering across many difficulty cycles. Initially, we soft fork to require the last bit of the block hash to be zero. The next difficulty cycle, we require the last two bits to be zero. We do this 16 times to get 2 bytes, and then we actually activate targets.

By then, nominal difficulty would have been cut by 2^16 (65536), but the block target makes mining each block 65536 times as hard. We do the progression over 16 difficulty cycles to minimise increases in block timings. We can be more specific and progress over even more difficulty cycles through more clever soft fork rules.

For example, Vitalik detailed "timewalking" attacks that allow effective granular lowering of the nominal difficulty.

Critique welcome.