Throttling malicious traffic through cost right at the source might be helpful.
Large relays can impose a cost as well, but it's difficult for them to distinguish between spam and a request that contains e-cash/has value without wasting some resources on spam. Perhaps a combination of rate limiting through PoW and hardware accelerated filters could help to reduce costs for large relays of they still face this problem.