I got lost in Valletta on Malta during a family trip when I was probably around 7 or 8, and it's one of my proudest and most formative memories from that period of childhood, even if it was scary as hell.
Valletta occupies a tongue of land thrust into the ocean. I got lost in the middle of the city, and had to come up with a plan for how to get back to my parents. I realized I'd probably be able to find it from the promenade as we had walked it a fair bit.
I recalled my Dad showing me the city map and pointing out the streets were on a very regular grid pattern perpendicular to the shores. So I headed down a street until I hit the shore. Then I realized I was on the wrong side, so I decided to round the entire coastline to get to the right, opposing shore. This was foiled by some sort of fenced-off military installation or something (scary!), but I was eventually able to make it to the other side by circumnavigating it. I got pretty close to our hotel when I ran into my Mom who was desperately searching for me.
My backup plan was to hover around streetside cafés looking for non-scary looking tourists speaking my language and ask them for help if it got too late.
It's so seared into my mind, I almost want to believe I'd still recognize the landmarks. I was definitely very scared and agonizing. But I've always felt very good that my plan worked and that I was able to get out of my first little crisis.
I'm not sure what the lesson of this story is. It's probably not to get your kids lost on purpose. Showing them a map of where they are and studying it together is great for sense of place and navigation, though -- make sure they know where they are at least roughly, not just that you can track them.