Fairly sure that Protect is 100% / 2^1 for Gens 2 and 3, and 100% on the first use and 50% on all consecutive uses in Gens 4 and 5. Bulbapedia backs up my knowledge, as do other sources such as Smogon. I can test in-game if you want, but it'll take a while.

From this post: http://www.smogon.com/forums/showpost.php?p=3718411&postcount=528 Seemed to imply protect was like gen 3 in gen 5. Also i need confirm for gen 3.

Seems like it'd be impossible to confirm in-game without a very large test (which I just don't have the time for, considering all 4 Generations Protect is in) or by checking the code of the games itself. If anyone else wants to test out how often Protect works after the first usage in a certain generation, please do so. If you do test Protect, be sure to not use a move that can break through Protect, and note which Generation of game you are using.

My own site contains descriptions for Protect from each generation: http://upokecenter.com/dex/?attack=182 Note in particular: Generation 2: A variable, X, starts at 255, [...] and is halved each time this attack is successful. This attack succeeds at an X/256 chance. Generation 3 and 4: A variable, X, starts at 0, [...] and increases by 1 (up to 3) each time this attack is successful. This attack has a 50% chance of failing if X is 1, a 75% chance if X is 2, and an 87.5% chance if X is 3. Generation 5: A variable, X, starts at 1, [...] and is doubled each time this attack is successful. This attack has a 1/X chance of succeeding, or 1/(2^32) chance if X is 256 or greater.

Whoah thanks a lot. Does this mean that in generation 2 protect always has a 1/256 chance to fail? (seems weird, so I edited the formula in PO a tiny bit to be consistent but don't hesitate to prove me wrong) Anyway I'll edit PO now, thanks again. (Also, you must get this a lot, but on firefox all your links are striked instead of being underlined)

You're almost right: it has at least a 1/256 chance of failing in generation 2. In generation 2, the first use has a 255/256 chance of succeeding, the second use has a 127/256 chance of succeeding, the third use has a 63/256 chance of succeeding, and so on.