I've been thinking a lot about my megadungeon, and I've come to one conclusion. I like the idea that every locked door should have a key somewhere. I don't like the idea of having to place, sort, and track all of these keys. Seriously, with hundreds of rooms per level, that's a lot of potential locked doors and treasure chests and whatnot.
So, never one to shy away from a video game reference (especially relating to the old 8- and 16-bit machines), I'm going with a video game approach to keys.
Find a key in my megadungeon, and it's like Schrodinger's Cat. It both is and isn't the key to any particular lock until the moment it's used in one. Then it is the key to that lock (and disappears...).
I figure this will save me lots of hassles, and will also not screw over the Thief. Thieves' Open Locks skill (and the Knock spell) become ways to save resources. If a party has found three keys, but knows of several locked and unopened doors/chests, every time the Thief manages to successfully pick a lock, they've saved a key for future use. And if the Thief fails, they can use a key they've found to open the lock anyway.
Keys would become another logistical resource management issue, rather than a headache of trying to remember if the key Blackwolf the Dragon Master took from the ogre in Level 3 Room 114 opened the door to the chest in Level 2 room 27 or the door to the Bone Cathedral in Level 7.
Down side? There go any sort of interesting locks/keys specials. Or at least it makes them harder to pull off without hurting immersion.