Immune does not and has never prevented characters from being killed outright. It only prevents damage and direct targeting, which makes it much less likely that your opponent is able to kill it. Non-targetted destroy effects can still affect immune characters.
Note the immune keyword description when highlighting a card in-game says “Immune characters can’t be damaged”. It doesn’t state that immune characters can’t die.
Edit: also, to respond to something mentioned in the original post, Kurtrus attacking the same minion twice when there’s only one on the board is also not a bug. In fact he originally used to only attack once in that case, but Blizzard specifically identified that as a bug and fixed it in this patch: