not requiring deposits for each recipient
Not sure what you mean here but just to clarify: we don’t need a separate deposit for each recipient, just enough deposited to be confident of paying the 1/1000 recipients whose tickets are redeemable.
You have a good point on griefing. 1000 of the one million recipients would see (offline) that the ticket will pay off, and send a transaction to the network attempting to collect. Only one would actually collect, so this would indeed be annoying.
However, that’s only the case if the spammer actually sends emails with insufficient deposits. Since this is much more expensive per actual reader ($10 instead of a penny), it’s more likely that spammers would deposit enough to actually pay the 1 in 1000 recipients whose tickets are redeemable. If that costs too much for them, then they have no profitable option.
Of course if someone’s sole purpose is to grief recipients, that’s another matter. If that happens often, a simple defense is to attempt on-chain redemption after a random delay instead of immediately (and only if the deposit is still there). I think it’d work for each user to make their own determination of the most profitable range of random delay, balancing the race to get the deposit against the waste of gas when they lose.
A nice side benefit is that the same system enables voluntary user-to-user tips.
For spam protection alone, PoW is definitely another option, though it’s not perfect; see Vitalik’s post here: Conditional proof of stake hashcash