An idea: could you, instead of removing freeze entirely, either replace it with flinching (to not affect things that use say, Sheer Force Ice Beam) or rework freeze so it's less random?
A thought I had, regarding the latter:
- Base thaw chance is lowered to 3%. The reason why will become apparent if you read on.
- Every turn that the thaw check fails, this thaw chance is multiplied by a number (let's say 3, for example purposes). This means you'd have a 9% chance turn 2, 27% turn 3, and 81% turn 5. This means it would be impossible to stay frozen for more than 6 turns.
- If the user has an ability relating to Fire (Flash Fire, Flame Body, Blaze, Turboblaze), this chance is further multiplied by 1.25; thus, things like Heatran would get a guaranteed thaw turn 5.
- If a move that would thaw the user hits a frozen target, it also thaws the target. (Unless moves have changed, this is only to close a loophole with Scalding frozen opponents.)
- A frozen target hit by a move that isn't Ice-type multiplies the thaw chance by 1.1; thus, getting a lucky freeze with Powder Snow and battering away with Tackle won't work for long. If a target with an already guaranteed thaw chance is struck by a move in this nature, the Pokémon will thaw immediately.
- A frozen target stops experiencing passive effects, and any turn counters on said statuses freeze with the frozen. Entry hazards also count as being hit by a move, and thus also fall under the former rule.
- This percentage will not reset on switch-out.
So... thoughts? Numbers are extremely, EXTREMELY malleable.