Sometimes a skill-focussed player can bypass entire obstacles with that skill. This is a shining moment for them (which you don't want to step on), but boring for the rest of the group.

The general principle I'd follow here is "Yes, but...", useful throughout GMing: Don't say no, but do say what obstacles arise as a result.

First, take a look at the rules. The skill description for Intimidate says that it can "force a bloodied target to surrender" or "cow a target into taking some other action". But that doesn't mean you control them. It doesn't say "unconditional surrender"; a typical minion might, but a King is likely to demand parole, the right to keep his weapons, and free passage for his men to leave - things the players might not be willing to grant. Also, the requirement for "bloodied" really means "the party has proved a convincing threat". I'd allow this check against non-bloodied targets in highly intimidating circumstances, and disallow it (forcing the second use of intimidate) in some cases - "berserk opponent" is pretty much an exemplar case.

Likewise, "taking some other action" just means that he doesn't make the attack he was planning. Maybe he gets cautious and retreats until he can gather more men. Maybe he agrees to negotiate, but he'd be negotiating from strength and likely to make demands the players can't agree to. (If this happened at the start I'd consider having him fight as normal, with a penalty for being uncertain - which goes away when he berserks. But you'd passed that point.)

The question to ask when you're deciding how he's cowed into taking some other action is: How does this guy behave when intimidated? Not all people react to fear by panicking: Some scream and run. Some keep their heads and run in a controlled manner. Some try to negotiate. Some look for another plan. Some get defensive and hostile. Some people get aggressive and hostile.

(And either of these last two are pretty likely for a berserker king. You said he wasn't immune to fear; you never said he didn't have berserk-refusal-to-surrender. Maybe he berserks, but has a -4 to defences the entire fight because he's swinging so aggressively that he doesn't defend himself. And he'll definitely attack the bard first - even if he's taking Mark hits from the Defenders for it.)

Finally, there's always "say yes, but reroute the plot to your ends". Suppose he's genuinely so scared of the group that he surrenders - how do his men react to this? Barbarian kingship involves keeping your throne by force - if he seems weak, probably his chief commander is outraged by his cowardice and challenges him for the throne on the spot. Describe a fight, and then whichever of them wins is angry enough to attack the players immediately - but they're already injured and berserk from the fight, so the players get to skip the first half of the combat, and they've used some of their powers up.

Or if he surrenders in return for letting his men go... another warchief is going to take them and attempt a rescue, or use the evil plan for himself, depending on loyalties.

That's the principle - let the party benefit from the skill, but the benefit isn't "miss all the fun".

If you want to avoid this situation in the first place, there's more work to do. A player who is entirely focussed on one skill will tend to beat any reasonable skill check you can throw at them. This isn't a bad thing; the opportunity cost of being that skill-focussed is not small and the player should get a benefit out of it.

For that reason, I would advise a solution other than "make it impossible in general". If you give every solo immunity to fear, you've not only removed the usefulness of Intimidate, you've also removed a range of possible villain personalities. Some arch-villains are cowards! (Not this one, obviously.)

(A berserker king probably should get Immunity to Fear when he's berserk anyway, so you'd be fine - but in this case you'd already passed that point. To give it to him all the time undermines what "fear" is.)

Instead, give solos resistance to fear. Make the player work for it.
(As GM I'd rule that the general +10 for "Hostile" isn't enough here. He's not just "enemy soldier" hostile, he's a berserker king being challenged at the height of his power by enemies who oppose a plan he's been putting great effort into, in a way that threatens his throne if he seems weak. That's good for a large circumstance bonus any day.)

Also, chaotic or neutral enemies may not feel bound to honour their surrender, if they get a chance to get loose.

You were right!

In that type of situation, everyone is ready to begin fighting at any moment. Everyone basically is 'readying' for their fight - not just the PCs.

Readied Actions

These actions do require a trigger to be specifically stated, as well as the action they will take if triggered. In a general situation, most Readied Actions take place during combat when the turn structure is in place. However, it may be possible to ready an action outside of combat, but you as the DM will need to adjudicate the possibility of that.

From the Players Handbook, page 193 (emphasis mine)

...you can take the Ready action on your turn so that you can act later in the round using your reaction.

First, you decide what perceivable circumstance will trigger your reaction. Then you choose the action you will take in response to that trigger, or you choose to move up to your speed in response to it...When the tirgger occurs, you can either take your reaction right after the trigger finishes or ignore the trigger.

Your situation

In order for the players in your situation to their ready action, they would need to have explicitly stated what their trigger was and what the use of their reaction would be. However, given that the combatants were also likely 'readying actions', the initiative roll works because everyone is on even ground.

Even if this was a one-sided readied action event (where the combatants whom the PCs were fighting were not prepared for a fight), the trigger for the PCs readied action is the attack - which needs to be completed before they can act.

In addition, a readied action is just that, something that is being held waiting for the trigger. That could be a caster having started their spell and waiting for the event to finish casting it (if no event, the spell slot is still lost), or the bowman with their arrow nocked and bowstring pulled and ready to fire, etc. etc. That sort of action may also move towards a specific resolution (FIGHT!) rather than hoping for an alternate resolution (NEGOTIATE!)

The developers have your back

Jeremy Crawford Tweeted about when Readied Actions are available.

The options, including Ready, in the "Actions in Combat" section (PH, 192–93) are meant to be used in combat, after rolling initiative.

but he also suggested an alternative:

Your readiness can guard against being surprised. Otherwise, you roll initiative as normal. The DM might give advantage

Jeremy also had a nice discussion on this podcast about readied action and initiative (starts at about 6:10).

Unspecified Initiative Rolling

There is a potential issue in how you roll initiative that should be mentioned. This section is not a judgement against the actions described, but merely a reminder to have a consistent and agreed upon method of initiative at your table.

If you are trying to create a level playing field, then you should roll specifically and openly for each combatant. While the DM does have "control" to make changes behind the scenes, what you have done is to allow the situation to play out as you wanted it to rather than be dictated by the rolls of the dice.

Even though you had one guy ready to go, you could have created a narrative around why the other mook got to go first - and that would have been a more consistent and fair way to adjudicate your initiative rolls.

The decision to assign the highest roll to the guy who was about to shoot may have further incensed the players and made them feel they didn't get the opportunity they should have. It doesn't mean what you did was wrong, but it may have contributed the feelings at the table. It may not have, but I think it's something you should be aware of and consider when rolling your initiative.