How about just going with the disk-based line if the candidate goes there? On-disk data structures is a rich area for exploration. I think you're getting people a little riled up here because you seem to want to discuss Bloom filters no matter what. You seem to grok that this should be about thinking skills, data structures, and algorithms. That's great. Forcing the candidate to go where you have a particular interest is not so great.
Unfortunately I myself am not too familiar with on-disk data structures and wouldn't be too comfortable interviewing based on that. It probably is something I should brush up on but for the specific role I've been interviewing for it doesn't seem to be a big need.
