While it's not SFIV, Playstation All-Stars has had tons of balance patches. At the start, Kratos was over powered, as he was very strong, had great range, had omni range with a few attacks, his attacks came out fast, combos were super easy, and his Super Attacks were pretty good. He had no blatant shortcomings. Since then, they've given some attacks less range, slowed him down a bit, balance his power a bit more (so not every single attack is really strong), and stuff like that. Of course, lots of other characters received changes overtime.
Also, PS All-Stars' latest balancing patch came very recently, and it was a very big one. So big, it got it's own trailer.
Just to give an idea of how balancing patches can go down.