Some grouped responses:
----------------------------------------
Regarding the clues and exploration based on that: While I get what you're after, I don't really agree that it's a fit for the game.
First, given that this is procedurally generated we can't just leave clues in a really obvious fashion around. What I mean is, the seeding logic would be such that sometimes a clue wouldn't fit, or would behind some giant plant, or whatever else. As the guy behind the procedural generation, I can tell you that's probably a time-sink of a month or so of coding to get that working right, spread over a 6+ month period. I just don't see it as being tenable.
Second, I also don't think that looking for clues would be very fun as a player. You're focused on being stealthy or attacking enemies, and not necessarily scraping every last bit of ground with your eyes. You're using the maps to navigate, which is pretty much exactly what maps are for. If the maps weren't there, and you came into a hallways with 11 doors, there's not much you can do other than open them all and then see what happens. And repeat, all the way through the building. The reason for the current scouting system is that it actually lets players just go to their direct destination.
I know that the whole clues thing is supposed to help with that instead, but I was just playing the Gerudo Trial thing in Ocarina of Time where they take away your map and make you find the last keys based on clues such as a popup when you approach the left or right door. It was... not fun. The dungeons where you actually have a map were way more fun, and I didn't ever lose a sense of exploration in Zelda simply because I had the map. And remember that Zelda is a hand-crafted game with something useful in every room, compared to here.
Third, with the clues thing, those would be about impossible to do art-wise. A bag of gems would look just like any other bag, presumably. Or a gem would be small and get lost in the scenery, as noted above. But when you get to more abstract things like "a boss is up ahead," that gets even more challenging.
Ultimately, this is only somewhat a game about exploration in the first place. It's a lot more about combat, choice, and so on. Anything that hampers the players' ability to make long-range choices is particularly damaging to the game. Hiding the maps makes for a lot of negative consequences, I think.
----------------------------------------
Regarding alternate scouting mechanics: I'm open to the idea.
Having buildings and exteriors be explored as they are now works because it's simple and new players "get it" instantly and intuitively from what I've seen. Potentially there's something better, though it's not a high priority for me to search for something like that. If somebody has a cool idea, I'm certainly open to it, though.
----------------------------------------
Regarding missions breaking the fourth wall: not much I can do about that.
The structure of missions is really important for clarity and player choice. That trumps the fourth wall for me. It's like how you have Quests that pop up from NPCs in other games, and which clearly break the fourth wall as well. In those you get even special icons showing in your main game view right above the heads of NPCs with quests, often. How intrusive! But we're all used to it.
Changing the missions to be more vague and story-integrated and harder to find would be the antitheses of where I'd want to take this game, honestly. The clarity of what your options are and what you can do (what you get as well as what the challenge is) are really something that this game revolves around at this point, I feel. That's where the strategic thinking becomes possible, which makes this not an RPG.
And yep, by breaking the fourth wall on occasion we move further and further from being an RPG -- but that's okay, RPG was never among the things this game was supposed to be. Strategy game is, and that's where anything that reduces the players' ability to plan or make choices quickly and clearly isn't something I want to do.
----------------------------------------
All that said, variety is good. If there were some ways to have some "untamed wilderness" areas that you could find, which didn't scout the maps for you but worked more like you described in that you can only go through them one at a time, it could be interesting. Though how exactly such an area might function I don't really know.
It's kind of a complicated matter and it's something that seems low down on the priority list to me at the moment compared to augmenting the existing game. Your prior suggestions about making background objects more interactive, for instance, is something I really want to do more of since I think it's a bigger bang for the time investment involved.
But having some more pure-exploration-centric areas, missions, or whatever could be very interesting down the line. And if folks have ideas on ways that the sense of exploration could be improved without cutting down on player agency or clarity, I could be really open to those, too.
