You may be interested in the work of Jean-Louis Reymond's group, who have done more or less exactly what you suggest: https://gdb.unibe.ch/downloads/
GDB-11, with 11 heavy atoms, has 26.4M structures (110.9M stereoisomers -- molecules aren't 2D). Going up to 13 gives you 970M molecules. Going up to 17 (still mostly below 250Da) is 166,400M.
There's a lot of space up there below 500Da.
Although including heavier elements can blow past 500 Da pretty easily.
Chemistry is difficult not because of the large number of chemicals but because there hasn't been a lot of structure discovered in them to allow the sort of compounding subcase solving that makes searching a sorted list tractable. The structure that has been discovered can be found in chemistry textbooks and has names like "so-and-so's rule" which can be applied to boroalkanes with between 5 and 12 vertices excepting 6, unless the cage is charged in which case you should treat it like it has one fewer vertex, unless the charge is -2 and the original vertex count is between 8 and 13, in which case...
Those rules are much better than a table as measured by information compression but you can't discover them unless you start with the table filled mostly filled out already.
It's only big if it's expensive to search all of them, and that problem is very easily parallelizable.
Which makes it a $$->time equation? If it costs 1s for 1 machine to check an item, you will need 32 machines to check a billion in a year, or 12000 to search in a day.
So, it's the is_match operator that's expensive, rather than data storage? Is the match check minutes long or needing human oversight?
But that is one of the expected applications of quantum computers (simulate quantum systems).
What makes 150 billion rows incomprehensibly large?
With a molecular weight of 500 we're talking something on the order of terabytes of data (for 1b molecules)?
It certainly sounds like a tractable amount of data.
What computer problems are stopping us from generating a compound, computationally testing it for stability, and adding it to the list and then searching?