In my experience, I don’t even need the illusion of choice, even meaningless choices add to the immersion: E.g. “You eat ice with your friend. What flavor do you choose?”. I immediately know that this choice probably won’t affect anything, but getting to make that choice still matters to me. What’s worse (and where many non-IF games also get on my nerves) is when there is a choice that feels like it matters, but when I replay the game I find out that it actually doesn’t.
Exactly, choice games can still have a world model, it’s just not built in. In theory you can convert any parser game into a choice game by just presenting a loooong list of all possible actions (though that would probably destroy the puzzles).
Choice of Games has 2 tools to automate this IIRC. One examines all possible branches and sees if the end can possibly be reached, but it makes some simplifications and is inaccurate because of that. The other tool is what you suggested: It uses random choices to get through the story, and does that many, many times to find dead ends and such.
If you can work in the rigid confines of ChoiceScript, it’s a good system with a big community around it.