In the replay that MikeDec showed, at turn 26, Rhydon dies before Chansey gets to move. With proper mechanics, this should result in Chansey not being able to move, but in the replay, Chansey gets to move despite the foe having died previously that turn. This is a bug.
The reason why Recover failed in that particular replay though, is that Starmie had (Max HP - 255) current HP. Starmie has 323 HP and had 22% when Recover failed. 323*0,78 is ~251 and 323*0,79 is ~255 (slightly above), which given how the rounding works on PS!, means that Starmie could and most probably had 68 HP (which is 323-255) at the time of using Recover. Therefore, Recover failing in that instance is not a bug.