I'm sorry, but even pre-tbc people had to amass 1k gold to learn epic riding. There was never, ever, a point where a character above lv20 or so could recieve a gold piece and confuse it with 'Vast riches"".

Okay i got really confused with this one and wandered around Scholomance for ages trying to find the way in.

Now my level for this is a little low so due to natural progression of the quests I probably would have figured it out eventually but for those who did the same thing that I did here is the quest chain for getting the skeleton key in order to enter the dungeon:

A Call to Arms: The Plaguelands
Obtained from any of the criers in IF, SW, or Darn. This quest will take you to Chillwind Camp in Western Plaguelands and have you speak to Commander Ashlam Valorfist.

Clear The Way - Chillwind Camp, Western Plaguelands
Starting NPC: Commander Ashlam Valorfist. This quest will have you Kill 10 Skeletal Flayers and 10 Slavering Ghouls in Sorrow Hill.

All Along the Watchtowers - Chillwind Camp, Western Plaguelands
Starting NPC: Commander Ashlam Valorfist. Using the Beacon Torch, mark each tower in Andorhal - 4 towers to mark

Scholomance - Chillwind Point, Western Plaguelands
Starting NPC: Commander Ashlam Valorfist. Speak with Alchemist Arbington in chillwind camp.

Skeletal Fragments - Chillwind Point, Western Plaguelands.
Starting NPC: Alchemist Arbington. Bring 15 Skeletal Fragments to Alchemist Arbington. This is the gathering of parts to make the key.

Mold Rhymes With... - Chillwind Point, Western Plaguelands.
Starting NPC: Alchemist Arbington. Bring the Imbued Skeletal Fragments and 15 gold coins to Krinkle Goodsteel in Gadgetzan. This is the crap part about getting the key, it will cost you money... and lots of it. Its easy but the 15g part sucks.

Fire Plume Forged - Gadgetzan, Tanaris
Starting NPC: Krinkle Goodsteel. Take the Skeleton Key Mold and 2 Thorium Bars to the top of Fire Plume Ridge in Un'Goro Crater. Use the Skeleton Key Mold by the lava lake to forge the Unfinished Skeleton Key. Again this involves money as the quest giver doesnt provide you with the thorium bars. Follow Goodsteel's instructions and take the unfinished key back to Arbington in Chillwind Camp.

Araj's Scarab - Chillwind Camp, Western Plaguelands
Starting NPC: Alchemist Arbington. Destroy Araj the Summoner and bring Araj's Scarab (to complete the key) to Alchemist Arbington at Chillwind Point, Western Plaguelands.

AND THEN FINALLY

The Key to Scholomance - Chillwind Point, Western Plaguelands.
Starting NPC: Alchemist Arbington. This is where Alchemist Arbington finally gives you the completed skeleton key to test.

Now you can go do the Dungeon! yay

https://vanillawowdb.com/?maps=2057:431281148392160834911669 Deed locations on a map.

Update: Wowhead changed the maps so the pins for many maps are currently broken. I tried my best placing the pins on the new maps:

https://vanillawowdb.com/?maps?data=2057:821460 Deed to Southshore
https://vanillawowdb.com/?maps?data=2057.1:312545 Deed to Tarren Mill
https://vanillawowdb.com/?maps?data=2057.3:379757838297 Deeds to Brill/Caer Darrow

Nowadays it's Solomance

Well, quest wasn't totally removed in patch 4.0.3, quest giver was moved inside of Scholomance. U can find him and four other quest givers just after entering instance.

At the top of this post it says Blizzard has marked the quest obsolete and it can no longer be obtained, or completed.

This is not true. Blizzard simply nerfed it for Cataclysm. It is now a level 40's 5-man.