I depleted the moves Twister and Stone Edge by using Spite. So the Gyarados wouldn't be able to hit my Misdreavous. I'm 100% sure that all PP were gone. Then the trainer withdrew Gyarados and sent out another Pokemon, which I defeated. Then he sent out Gyarados again and it could use Stone Edge again. Even 3 times in a row.
What could be the cause of that? I think there's something missing to tell the game to save the amount of PP.