I installed this mod because I wanted to go crazy with randomness but not have to deal with spaceflight at the same time:
https://mods.factorio.com/mod/EverythingOnNauvis

However, installing this seems to break the random recipes option, as it would consistently require an impossible item to get. For instance, in one seed the basic transport belt (an ingredient for red science) required tungsten ore. Another try I had something in the chain of resources for green science require pentapod eggs. A third try had something vital requiring lithium.

While those could technically be picked up (boulders containing small amounts of ore, pentapod eggs on the ground, lithium from the ice rocks), it would be near-suicidal to try picking those up without starting military science at least a little bit, not to mention the fact that it would require hours of scouring the map (on foot, since no vehicles or power armor yet) to pick up enough of them to make any amount of progress.

I'm guessing there's something in the recipe randomizer that normally excludes impossible things on Nauvis, like Uranium ore not being required until at least after sulfuric acid is unlocked, but those being pick-up-able somehow bypassed it? Since normally things like fish are excluded from most recipes because you can't manufacture endless fish, I think that sort of thing ought to be in the same category, but they weren't similarly excluded.

The tech tree with the mod installed does still have the techs for these things (like biolabs) pretty far down the tech tree so I assume a tech-tree based filter for the ability to manufacture things would have worked, unless it does something funny with techs that are trigger-based instead of research-based, since the 3 items I've noticed this happens with so far all should only unlock after both a tech tree milestone and a triggered unlock.

"Everything On Nauvis" may have been the mod that triggered this for me, but there's probably a bunch of other ones out there that would break it similarly with other custom resources put on Nauvis with similar traits (i.e. can pick up in tiny amounts, but not manufacture or mine in bulk for much longer). So a general solution, rather than an exception for this one mod, would probably be beneficial.

Currently, this is solved with manual blacklists, but I currently have new logic (just released, but not used for much yet), that can test if something is automatable, not just "could you technically get it". This is sort of what you were on about; it's actually not that these things are "impossible" but rather that they are possible that is the issue. Randomizer senses this and allows them to be in recipes as a result.

The issue with using the new automatability capabilities right away is that adding that new constraint causes the randomizer to fail a lot since it already has a lot to work with, not to mention all the current non-unified randomizations use old logic that does not have this capability, so it will be a while before this is fully implemented. For now, I've given up on mod support (you may see some other threads here with similar issues). I hope to be able to support mods eventually though, as I've done a lot of work to make things potentially mod-compatible.

I have thought also about shortcuts like just looking if something is further down in the tree, if there's a current recipe to make it, etc., but that didn't feel satisfying so in the end I just have gone with designing the biggest hammer I can. Of course, this means things will also take a while and may not even work as well as if I designed special cases for each modpack, but it's what makes me happy and that's what matters.