If someone does end up in a spam list (and they don't rack up a high score across multiple targets), let them know they're in such a list and where to start looking to resolve that issue. A good enough solution for this is to have number carriers attest to have verified the government issued ID of the individual in question; and if spam happens shortly after that to yield the government ID number of that individual.

An alternate form I've considered, for email, is to pay a postage (transfer + storage) micro-transaction fee, and possibly an attention fee for prompt review. The custom might be to refund these in cases of legitimate messages.