Oh, I was thinking of how eg GMail could do it.

It depends a bit on volume of spam compared to legitimate emails. GMail knows about all of your past outgoing messages anyway, but the bloom filter would allow to quickly drop spam.

Google is already using Bloom filters to eg check locally in one service whether a cache in a different service is likely to be able to answer a query.