Poison comes up rarely enough (once every other play session at most) that poison immunity isn't very likely to be game-breaking.
As for dwarf kings being poisoned in the past, I concur that if one shows up dead by poison that it is an intriguing mystery, not an irreconcilable problem. A king being poisoned in a fantasy setting is mundane, but a dwarf being poisoned is news.
I especially like that if dwarves are immune to poison, they won't take any precautions to protect their king from a poison plot. So if a king does wind up poisoned, it takes extraordinary means to track down the killer.
Actually, this reminds me of the novel Cormyr, where King Azoun was poisoned. How do you poison a king who has wizards and clerics at his beck and call that can undo any assassination attempt? There, they had magic dead zones around the toxin (or virus I forget) forcing the mages to leech him, teleport the blood to another container, and give him blood transfusions of his own blood.