The "Legal or not" part of your question is interesting. I am guessing you mean a "legal" board is one which was derived from the starting position following the legal moves. How could this be determined, short of doing a brute force search from the starting position?
This is something I've thought about when looking at chess problems, whether such problems could actually occur in a real game.
I wonder if existing computer chess engines can be modified to do retrograde analysis, and then find some heuristic for positions that are "obviously" possible via legal moves, and then see if the retrograde analysis can reach one of those.
I have a feeling this is often tractable, because we could probably construct a cooperative scenario involving sacrifice of arbitrary pieces at the beginning of the game (maybe via a series of knight captures?), and then the main question is confirming how particular pawns moved past each other, and finding a way of ensuring that no stalemates occurred while positioning the kings.
(because apart from the structure part that the link you gave mentions, experts seem to know a huge amount of explicit opening theory, in terms of memorized opening lines and particular chess masters' view of their tactical consequences)
I'm getting more curious about the reachability question.
That includes a retrograde solver for openings, but that's not exactly what I was envisioning -- I was thinking of a retrograde solver for endgames, which then needs something kind of akin to an inverse tablebase ("yes, this family of positions is known to be legal!" instead of "this position is a win for black").
It's an interesting question. It is easy to check when a position is unreachable, sometimes.
For instance a white king on H8 and black Rooks on A7, A8 (unless I'm mistaken).
It almost seems as if it is easier to find a position that is guilty (when it is), than to check that a position has a perfect record (check that it is legal).
This is something I've thought about when looking at chess problems, whether such problems could actually occur in a real game.