Good post and I'll chime in if you don't mind. I teach this stuff for a living and even highly skilled musicians struggle with it in various ways (myself emphatically included).

The main thing I want to say is that there's a reason why essentially all music education consists of many years of rote learning. Obviously, that rote learning works better if it's guided in appropriate directions, but I really don't know of any alternative to what you describe when you say "an orders-of-magnitude-less-efficient mechanism for memorizing note-to-note mappings for every note and every pair of keys." I hate to say it, but ... yep. [EDIT: eh, let me qualify that a bit. See point (A) below.]

Sight-transposition (i.e. sight-reading plus on-the-fly transposition) is a ninja-level skill. Some instrumentalists (usually those who play non-concert-pitch instruments) can do it reasonably well for at least some transposition intervals, and a few people like professional vocal accompanists and church organists need to be able to do it fluently as an expected part of their job. But outside of those folks, even professional musicians rarely have that facility.

Here's something that directly supports your point at (D). As you know, pitch intervals in tonal theory are given names that break arithmetic—a second plus a fourth is a fifth, even though 2+4≠5. A certain well-known music theorist often expresses the view that this blatantly illogical convention is almost entirely responsible for the popular perception that music theory is a really, really difficult subject. I think this exaggerates things, but he's got a point. However, most musicians know those interval names really well and have never thought much about how stupid they are, and so then high-level music theory becomes opaque to skilled musicians because we start by renaming intervals correctly (i.e. a second is diatonic interval 1, and you can add them like normal numbers).

In the case of the frustrating conventions of staff notation, there are historical reasons going back a millennium why we write pitches like that. Various reforms have been proposed, but path-dependency basically makes it impossible that any of them would ever be adopted. Far more likely (and well underway for decades now) is that musicians will stop using notation altogether.

Just to briefly answer your other questions with my personal views:

(A) Personally yes, I have all the note-to-note mappings memorized. I do this completely via thinking in scale degrees. I can name any scale degree in any key, so questions like the one you mentioned just revolve around thinking "B-flat is scale-degree 4 in F major. What's scale-degree 4 in C or A-flat?"

(B) Yes, I do think this is plausible, and underappreciated in the specific case of music, since most musicians don't think much about the ways in which notation isn't an optimized system.

(C) Maybe this is too glib, but ... social interaction? "Overthinking it" isn't a path to doing well in social settings. For that matter, natural language might be another. In many respects it's best learned by rote (along with some theory—just like music) but I've certainly had classmates in language courses who get too hung up on the illogic of grammar to progress well in basic skills like speaking and listening comprehension.