I always thought the black pudding was a royal headache for CR 7; immunities, a ton of HP... plus, difficult to fight with weapons (because it eats them). Many PC's still tend to be poor at this level... many are not yet flight-capable yet, either.

Martial characters are largely useless against these, except for maybe a charge/pounce-build, who happens to have an expendable blunt weapon on-hand.