Tats,
can you afford some intermediary false positives? If yes, the Bloom filter will scale. It dramatically reduces space requirements and lets you play 'divide and conquer'. You set up e. g. 100 filters and test for hits. Your search space is down to 1%. As the bloom filter will produce some false positives, a proper retest is needed. But it will quickly weed out sure non-hitters.
It has disadvantages:
1) Just hit/miss info. Not X matched Y.
2) Fixed lenght and
3) exact only.
But fast. Even if it sounds impossible, please do the math for a brute force fixed length approach.
Perl.com has a good article on Bloom filters and CPAN has Bloom::Filter by the same author.
In an unfinished hobby project I based the Bloom filter operations on Bit::Vector instead of pure perl vec and got a huge speed increase (more than tenfold, increasing with size). If you use Bloom filters in your project, you owe us a C implementation :-).
Given the estimated run time for other approaches it might be feasible to get easy results quickly. For a bloom filter that is exact matches.
Hope that helps,
Johannes Nieß