Do other spam filters actually check every incoming email against a database of outgoing emails?
And perhaps empty it once a year, if necessary. (Ie so that replies to emails older than a year don't rank better than random emails.)
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.