Is your ultimate goal to simply estimate how many of the strings are unique (or conversely, how many are duplicates), and possibly provide a confidence measure for the estimate? Or are you hoping to come up with an exact number of actual uniques/duplicates for the whole set? (Based on your stated plan, it seems clear that you aren't trying to identify/enumerate the unique strings.) If you're just looking for an estimate, why not work on a manageable and reasonably sampled subset of the data?

In my linguistic background, "several" usually means "more than 4, less than 10". If that's what it means for you as well, and if syphilis has provided a valid metric, then once you're done processing the first 4 billion strings, each new string will definitely be counted as a duplicate, regardless of whether it's a true or false positive. (Perhaps that's not exactly an absolute certainty, but it seems close enough.)