One option would be to either by default or by a user enabled option don't use change outputs until they have at least 1 confirmation.  That combined with simply "hiding" duplicates would make the mutated spam pretty much invisible to "normal users".  Merchants and service providers not using a payment processor need to understand the mutability of txids but honestly they already should.