DKIM is hardly a PoW; signing is cheap and gets cheaper all the time. I used to work in the email business and big bulk mailers all spent far more CPU time on other aspects of their business, the overhead of DKIM is irrelevant.
PoW didn't work in the anti spam world because it (amongst other problems) mixes up bulk mail and spam, which are not the same thing. Very common conceptual error though.
humans also don't care if their patience is put to the test by having to
wait until one Tor exit node is finally unbanned, or by waiting for
the connection PoW to finish because it temporarily got harder due to
an attack.
They don't? This is news to me. Humans always care. One of the surest ways to hurt your online business is to have a slow website because lots of users will give up rather than tolerate a few seconds of latency. At Google we actually had formulas that could relate a change in web search latency to revenue impact.
So humans very much care! I actually doubt that any reasonable mobile wallet will use the new Tor support bitcoinj by default, for example, because it imposes quite some startup cost when the downloaded consensus isn't fresh, and slow startup is painful. It could be optimised but nobody has done that. For long running desktop wallets where startup time can be amortised over hours or days, I guess it makes more sense.
I agree that PoW tokens might make sense as a last resort if nodes can't even put a connection at the bottom of a priority queue and you're right that it may be a useful tool in a shared toolbox. However if we reach the point where users are all being PoWd then we're already pretty hosed and it's probably close to game over :(
I'd say, better have a few Tor-based users realize that they
should look for a fixed update because their client has to do PoW for
connecting, rather than having all Tor-based users locked out.
I think Tor is a separate issue. If an attacker wants to either force all users off Tor, or force them via a handful of exits, then this attack is quite detectable already and wallets could already decide to simply give up on Tor at that point automatically. No PoW needed. Well, ideally, nodes would disconnect a banned IP with some kind of notice saying why it was banned, but that's a small improvement.
Still, users should be notified that something is unusual.
If we're talking mainstream success then users by and large do not care about technical mumbo jumbo like peer to peer networks or Tor ("that's the thing drug dealers and pedos use???"). They just want the damn thing to work reliably. So notifying them is unhelpful - it's not actionable. They would just see a message like
"The wizzle sprocket is kaput - keep working? YES NO"
and then everyone presses yes.
Stuff like Tor plays well in the crypto community but it's very hard to actually switch on by default, because it needs to have absolutely no cost at all, otherwise you'll just annoy the vast majority who don't want to pay for very abstract and hard to quantify privacy benefits.
So I think it's worth considering the DoS problem and Tor somewhat separately, even though they're related. The solution to a crafty privacy-attacking DoS that tries to make exits useless is don't use Tor at all. The solution to "the entire Bitcoin network is under attack" is much harder. It's unclear to me we can ever solve it convincingly - banks don't connect together using private networks in which anonymity is forbidden because they're stupid. They do it because it solves DoS attacks in one solid move and they feel it's worth the high cost.