Talk to Hreidmar outside the east entrance of the palace.
Talk to one of the protesters and ask them where Meike is.
Head to the King's Axe Inn (West Keldagrim) and talk to Luitger. Ask him why he didn't join the protest.
Go to the Black Guard HQ (west of the bank) and talk to Klaas and ask him where Meike is.
Go to the Top of the Watchtower (South of West Keldagrim) and talk to Meike (Chat Options 3,1)
Tell her to meet you at the Library.
Go to the library (North of the palace in West Keldagrim) talk with Meike then ask the librarian to open key case.
Unlock the cabinet and use the soft clay on the cabinet.
Use the soft clay on Meike and then talk to the librarian about the keys.
Then return to Meike.
Make copies of the keys using the mithril bars and moulds with a furnace (there are none in Keldagrim and a portable forge will not work)
Go to the Records Chamber located west of the Black Guard HQ.
Speak to Meike or Veldaban and match up the keys with the correct keyholes. The correct combination to unlock the door is (from southern-most keyhole to northern-most keyhole): 5, 1, 4, 6, 3, 2.
Open the door.
Routing the chaos dwarves
Note: Prepare for battle against Colonel Grimsson, who is level 84.
Defeating Colonel Grimsson
Items recommended: Combat boosting potions and food
Talk to Veldaban and ask him to lead you to the Barendir caves.
Enter the cave and travel north-east- all the way to the opposite end and speak to Colonel Grimsson.
Defeat Colonel Grimsson while making sure that Veldaban does not die.
For a guide on a more detailed version of this fight click here.
Recruiting the trolls
Speak to Veldaban (Chat Options 3-3-Any-3).
Head back halfway through the caves until you come to an entrance on the east side, enter it and speak to Pretty Flower (Chat Options 2-2).