So, I've been doing some thinking about my procedural puzzle game generation algorithm, and I've come to a few more conclusions. When I've come to a sufficiently large number of conclusions, I'll probably re-write that article, or make it a page, or both.
Here's the first thought: I don't know why I put "make a start node" as the first step, since what really matters is just that the graph itself be generated first. Then, if you like, you can select the start and goal nodes. The reason that this realization is important is that it'll free me to up generate the world much more organically and less prefabricatedly (maybe), and then worry about the locks and keys.
Here's the process I'm going to try to follow for generating the world, then. (NOTE: I haven't done any research on this, so these steps are just off the top of my head and will probably fail to work completely.)
With all these steps done, we'll probably be in a position to run the rest of the algorithm and actually lock down these "edges" (connections) and place keys around the world. I'm going to try it out!