I know it can fail, because it happen to me 2 times.
Critical Captures just perform one shake check instead of 3, and those depend on the Pokemon's modified catch rate which comes out of this formula:
HPmax is the number of hit points the Pokémon has at full health, HPcurrent is the number of hit points the Pokémon has at the moment, rate is the catch rate of the Pokémon (which may be modified due to use of the Heavy Ball or actions in the Safari Zone), bonusball is the multiplier for the Poké Ball used, and bonusstatus is the multiplier for any status condition the Pokémon has (2 for sleep and freeze [2.5 in B/W & later games], 1.5 for paralyze, poison, or burn, and 1 otherwise).