Lets suppose Bob was a spammer pretending to be a mailing list operator.

Alice gives her key to Bob, in the expectation that Bob would not be sending her spam. Bob then sends both spam, as well as legit mail that alice did want. Assuming that alice does not want to stop receiving the legit mail, but want to stop the spam, how does she do it in this scenario?

If alice blacklist the key for bob, but sends a new one, the situation didn't improve. If she doesn't send a new one, she stops receiving legit mail (that she wants, and cannot go without).