I think the Bloom Filter is the best option here. Does anyone have a different/better option?

One of those times I'd reach for a database. SQLite should cope with a few million rows quite happily.