This happened to me repeatedly with my six character party. I was saving the legendary run for Into the Eye with my four character group until my six character party caught up, but then I stopped playing in the hopes that this ever vanishing Karzoug would be resolved. Any word?
Also, the last scenario isn't all that tough as long as you're patient. Keep people healed and make sure you fight when you want to fight. Get Karzoug on the bottom of the deck and then make sure nothing happens to reshuffle it. I've finished it up through heroic (or whatever the middle thing is called) with one group and then I stopped a few weeks ago until I was fairly certain the Karzoug thing was fixed. My six person party faced him as the last person in the deck three times where all the pre-fight stuff would resolve and then he'd just go back into the deck before battle. At that point, I looked around for the hidden camera and group of psychologist taking notes on the effect of major frustration on a gamer.