So in order to help players who've forgotten - or never did them in the first place - I decided to collect some information about various keys and attunements in one place so you don't need to trawl through multiple sites.
1) SCARLET KEY
-required for SM Armory and Cathedral
-after killing Arcanist Doan in SM Library, the key is lootable from a chest by every party member
2) SCHOLOMANCE KEY
-required to enter Scholo but can be bypassed by a rogue with high enough lockpicking
-this is a long chain that starts with the following quests:
Alliance: http://db.vanillagaming.org/?quest=5092
Horde: http://db.vanillagaming.org/?quest=5096
-next part is: http://db.vanillagaming.org/?quest=5098
-then to the forging:
Alliance: http://db.vanillagaming.org/?quest=5533
Horde: http://db.vanillagaming.org/?quest=838
You will need the following mats during the chain, which you should get beforehand:
2x Thorium Bar
3) SEAL OF ASCENSION
-required to enter Upper Blackrock Spire
-collect 3 gems and unadorned Seal of Ascension from LBRS. The last one drops randomly from all mobs, the gems drop from Wyrmthalak/Omokk/Voone. You can have all 4 in your inventory without getting the quest first. The NPC is inside LBRS, hidden in a cave.
http://db.vanillagaming.org/?quest=4742
-second part is to mind control Emberstrife, a level 60 elite wyrm, to breath the Flame of the Black Dragonflight, on the quest item.
http://db.vanillagaming.org/?quest=4743
4) KEY TO THE CITY
-required to enter the Scourge side of Stratholme, making Baron runs easier, though the doors can be lockpicked
-drops off Magistrate Barthilas
5) WORKSHOP KEY
-backdoor to Gnomeregan that allows party to skip most of the instance to reach the emissary (rare) and the final boss quicker
-drops off Electrocutioner 6000
6) DRAKEFIRE AMULET
-required to enter Onyxia's Lair
-VERY long chain that starts with
Alliance: http://db.vanillagaming.org/?quest=4182
Horde: http://db.vanillagaming.org/?quest=4903
I'm not going to detail the quests in here, that would take up too much space. Needless to say, you will have to raid multiple dungeons and travel around the world.
7) ATTUNEMENT TO THE CORE
-allows you to be teleported inside MC without going through BRD
-get a Core Fragment from BRD and give it to Lothos Riftwaker: http://db.vanillagaming.org/?quest=7848
8. HYDRAXIAN WATERLORDS
-Duke Hydraxis gives out Aqual Quintessence needed for dousing the flames in MC after killing a boss
-starts with quest http://db.vanillagaming.org/?quest=6804 which is doable before hitting 60, so a good idea to get it done.
-once you reach revered with them, you should be able to get Eternal Quintessence but this was introduced in patch 1.11 so whether it exists on Nostalrius yet is unknown. Please share your knowledge if you have already grinded the reputation!
9) KEY TO SEARING GORGE
-allows Alliance to enter Searing Gorge from Loch Modan
-started by getting Margol's Horn in Searing Gorge: http://db.vanillagaming.org/?quest=3182
10) MALLET OF ZUL'FARRAK
-required to summon Gahz'rilla
-get Sacred Mallet from Qiaga the Keeper in Hinterlands and take it to the nearby altar
11) SHADOWFORGE KEY
-required to skip parts of BRD and to enter the Grim Guzzler bar instead of having to have rogue pick the locks.
-started by a quest that you can only get in ghost form, outside of the instance. So once you're in BRD, keep your eyes open as you run back after your first wipe.
12) CRESCENT KEY
-required for Dire Maul North and West parts
-drops from Pusillin in DM East
13) DRAKKISATH'S BRAND
-required to enter Blackwing Lair
-started by getting a quest item off Scarshield Quartermaster near the entrance to Blackrock Spire and requires a UBRS raid
14) SCEPTER OF CELEBRAS
-teleports you to the last segment of Maraudon for quicker Princess runs
-starts with http://db.vanillagaming.org/?quest=7044 from an NPC in Desolace and requires you to kill Noxion in orange part and Vyletongue in purple part, then talk to Celebras the Redeemed after defeating him.
-note that this quest was bugged at launch but has since been fixed so if you skipped back in the day, you should go back to Maraudon and complete it now
***No point in adding AQ War Effort or Naxx attunement at this point***
If I've missed anything important or you feel that there should be additional details, let me know.