Unfinished Gordok Business

1. Enter instance - Do Not Kill Guard Mol'dar (69.63, 75.05) (Important - If you kill him, you can't complete the quest and will need to exit & reset the instance, then he will attack you until you kill the King again - avoid him by killing the dogs to his right, carefully so as to not aggro him)
2. Click on the chest at 49.35, 78.41 to get the Gordok Courtyard Key
3. Speak to Knot Thimblejack (28.58, 55.22), take the quest The Gordok Ogre Suit
(optional, no reward or rep) 'fix' the broken trap, trapping Guard Slip'kik - one less to kill
4. Go up the first ramp, collect the Ogre Tannin (basket 23.65, 55.32) - Bring it back to Knot, get the Gordok Ogre Suit, put it on (lasts 10 minutes)
5. Go up both ramps, through door, speak to Captain Kromcrush (31.74, 48.77) - he's now standing where you got the
6. Go forward, kill King Gordok (31.70, 26.02) - speak with Mizzle the Crafty (31.76, 27.48) - collect loot.
7. Head back towards the entrance
8. Speak to Captain Kromcrush (he's now standing where you got the Gordok Courtyard Key) - Get quest Unfinished Gordok Business
9. Speak with Stomper Kreeg <the drunk> (67.87, 66.01) - Get quest The Gordok Taste Test - (optional, no rep but get 5 Gordok Green Grog and 5 Kreeg's Stout Beatdown)
10. Speak with Guard Mol'dar - complete Unfinished Gordok Business

EDIT: As I was compiling this, I was hoping to get some rep for Steamwheedle Cartel - unfortunately, this was NOT the case.

Notes on Thora's instructions, after Cata and Mists have dropped:

1) Enter Dire Maul north - that's the one this quest takes place in.
2) No longer necessary since the removal of keys. [object=179516] is now empty and the door is already unlocked; just go straight through.
3) No change.
4) Thora's instruction and wowhead's map for this quest are correct, but Blizzard's in-game quest marker is incorrect. It puts the location much farther along in the instance than it actually is. Follow the instructions here, not your in-game map.
5) [npc=14325] wasn't standing where I got the... tannin, I'm guessing? Anyway, he's all the ramps and down the hall, just before you enter Gordok's Seat (the circular room with [npc=11501]).
6) Kill [npc=11501] but make sure to leave [npc=14324] alive.
7) No change.
8) Well, where you would have gotten the key in step (2) if it was still in game. You can't really miss him, though, as you're running back towards the start.
9) No change.
10) No change.

Hope this helps some folks. Thora's original comment quoted below:

1. Enter instance - Do Not Kill [npc=14326] (69.63, 75.05) (Important - If you kill him, you can't complete the quest and will need to exit & reset the instance, then he will attack you until you kill the King again - avoid him by killing the dogs to his right, carefully so as to not aggro him)
2. Click on the chest at 49.35, 78.41 to get the [item=18266]
3. Speak to [npc=14338] (28.58, 55.22), take the quest The Gordok Ogre Suit
(optional, no reward or rep) 'fix' the broken trap, trapping Guard Slip'kik - one less to kill
4. Go up the first ramp, collect the Ogre Tannin (basket 23.65, 55.32) - Bring it back to Knot, get the Gordok Ogre Suit, put it on (lasts 10 minutes)
5. Go up both ramps, through door, speak to [npc=14325] (31.74, 48.77) - he's now standing where you got the
6. Go forward, kill [npc=11501] (31.70, 26.02) - speak with [npc=14353] (31.76, 27.48) - collect loot.
7. Head back towards the entrance
8. Speak to [npc=14325] (he's now standing where you got the [item=18266]) - Get quest Unfinished Gordok Business
9. Speak with [npc=14322] <the drunk> (67.87, 66.01) - Get quest The Gordok Taste Test - (optional, no rep but get 5 Gordok Green Grog and 5 Kreeg's Stout Beatdown)
10. Speak with [npc=14326] - complete Unfinished Gordok Business

Done in BFA 8.2. This for how to solo this after the removal of the keys and to maximize your chances to get loot from the [object=179564] chest. If you don't care for getting maximum chest loot, then make sure you don't kill Guard Mol'dar and that you get the ogre suit and talk to Captain Kromcrush.

Full Tribute Run (skip this if you already know how to do one):

1. 
   
2. Skip all bosses (including extra bosses) except for King Gordok
3. 
   
4. After entering the hallway after Guard Fengus area, go until you see a hunter looking trap (Broken Trap) on the ground. Complete its quest (but avoid aggroing Guard Slip'kik)
5. 
   
6. Wait for Slip'kik to get caught in the trap and then work your way up the ramp
7. 
   
8. When you see the brown basket in the middle, click on it to get the [item=18240]
9. 
   
10. Go back down the ramp to the goblin next to the fire (Knot Thimblejack) and turn in the tannin to get the Gordok Ogre Suit
11. 
    
12. Use the suit and go up the ramp until you see Captain Kromcrush. Talk to him to trigger him to leave.
13. 
    
14. Go to the King Gordok and only kill him; don't kill [npc=14324]
15. 
    
16. Wait for Mizzle the Crafty to come and keep talking to him until he spawns the chest and loot it.
17. 
    

Quest Steps:

1. 
   
2. Do a "Full Tribute Run" (or do the minimal parts to get Kromcrush back to the courtyard)
3. 
   
4. Head back to where Guard Fengus would be fought at and talk to Captain Kromcrush
5. 
   
6. Accept the quest and turn it into Guard Mol'dar
7. 
   
8. gg
9.