What happens to these seemingly unique items after earning them from the puzzles, especially if I don't locker them? I don't want to lose any of these items! Do they appear randomly in the dungeon shops or something now?
Yes, once you unlock the items by completing the puzzles, they will appear randomly in shops. As you said, immediately placing them in a locker is the best way to ensure access to them, but since you only have so many locker slots you won't be able to do that with everything. The rest you'll just have to wait for them to make an appearance every now and then.