Okay, so you’ve written a fantasy story. The heroes go to the kingdom’s capitol, they go to the big castle in the middle, and they ask to see the king. What did the guards at the gate tell them? I bet it wasn’t ‘sorry, he’s not in.’
Yet maybe it should be. One thing to remember about medieval kingship (you know, just generalising across loads of countries and the better part of a thousand years, as you do) is that kings didn’t often just sit in their main castle, wearing a crown. Indeed, when they did, it was often an indication that they weren’t that strong, and so didn’t have control over a big enough area to go anywhere else.
Kings actually travelled about quite a bit. There were wars to attend to, for one thing. Medieval kings were forever wandering off on them, leaving their countries to be run by assorted regents, and then having to go to war with the regents to get them back afterwards. Between the Third Crusade and his imprisonment afterwards, Richard the Lionheart probably saw more of foreign parts than of his own kingdom.
It wasn’t just wars though. Medieval kings were often itinerant. They moved between castles, palaces, the homes of prominent supporters and the homes of people they thought ought to be prominent supporters and who needed a king sitting in their living room to remind them of whose country they were living in. They stayed the night in monasteries and inns, stately homes and occasionally tents, usually dragging their entire courts around with them. There are whole sections of historical effort that go into using the ‘signed by the king at such and such a place’ bit of charters to work out complex pictures of their travels.
They did this kind of thing for a few reasons. One was that it allowed them to project their power and remind people who was king. Often, the early years of a reign meant that they travelled with an army and effectively reconquered their own kingdom, or at least asked in very pointed tones if anyone had anything they wished to say about them being king. They would go around collecting homage, or the formal acknowledgement of their superior status when it came to bits of land. One particular embarrassment for successive English kings was being made to do homage to the French ones for Normandy, and a good barometer of their relative power is whether they could be persuaded to actually do it.
There was also a simpler economic reason for it, which is that royal courts consisted of lots of people, and thus were terribly expensive to feed and house. It was easier and cheaper to move around than to stay in one place. Especially with other people hosting them (footing the bill).
It wasn’t just kings, of course. Archbishops had pretty regular itineraries, moving between archiepiscopal palaces, the nice bits of minster churches, and their own cathedrals, taking a large staff with them. Bishops did it, and so did some major barons. Lesser lights might have followed a particular court around, or set off on their own journeys around the regular stops on something like the tournament circuit (as William Marshall did for a bit). Even the supposedly stable Cistercian monks seemed to spend half their time going back and forth between General Chapter meetings.
The point is that important people in medieval societies moved around a lot more than people sometimes give them credit for. So the next time your heroes are looking for a king, why make it easy? Send them out trying to catch him up instead. Or better yet, have him show up with three hundred of his closest friends, expecting a bed for the night.