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.