Yes, indeed. I suspect there's a quick hack that could make this problem a lot better though.

I think I brought up this idea before, but can't quite remember. Anyway I'm willing to bet that if we analysed the data some more, we'd discover that most "legitimate" i.e. non-DoS unconfirmed transactions that sit around for ages are linked back to the block chain within two hops and not more. That is people send a transaction that uses up their coin age, and then immediately those coins are immediately respent again, but then those final new coins are not spent.

On the other hand DoS attacks look like bouncing your coins around over and over forever, i.e. more than two or three hops back to the chain.

So I wonder if making priority look back two or three transactions but not more would help real users a lot, whilst not opening up any significant new potential for DoS.