The duke... The answer DOES lie before the wastelands. And so does every other quest. Once you hit that gong, you can't come back to solve the quests, and plus you'll fail all your running quests. So finish them first, if you want to.
Shrimpo... How can I say this without much spoilers... Let's see... (Stop reading tips if you think you know it.)
Tip 1: He's near the graveyard.
Tip 2: You can't find him litteraly. You have to trigger something first, then he'll come to you.
Tip 3: What to graveyards have?
Tip 4: Tombstones, right?
Tip 5: So then let's find some tombstones... But which ones?
Tip 6: Some tombstones have writing on them.
Tip 7: You need a combination of tombstones...
Tip 8: Look very carefully at what the tombstones say.
Tip 9: Look at the letters.
Tip 10: Try and find a combination that makes sence...
Tip 11: Spell out a word somehow.
*phew* Now you're on your own.