Yes, there's only a 50% probability of everyone surviving, but each individual has a 99.5% probability, coming from 50% if they are asked first and 100% otherwise. I think it's one valid way of reading hyperpape's statement.

It seems not so easy to calculate, unless I am overlooking something obvious. Therefore I chose to be lazy an wait for the answer, if it is correct or similar then calculate

Your solution makes sense for sure, like in the case of two boxes. But I feel (just feel, no reasoning) that there should be a way of making better use of the information that comes from the fact that the previous prisoners could find their names. But maybe you are right my solution may even be worse than that. curious about the answer

Greater than 30%

First of all, the first prisoner (let's call him A) can't have a better chance than 50%, since there is no information available at the beginning.
Also, since the puzzle is symmetrical with respect to the numbering of the boxes, it doesn't really matter which boxes the first prisoner opens, so we can just assume without loss of generality that he opens the first 50 boxes.

What strategic decisions can the second prisoner (let's call him B) make?
The only information he has available is which boxes prisoner A opened. So when B decides which boxes to open, he can decide to open a number of boxes from 1..50 (let's say N boxes), and the other 50-N boxes from 51..100.

Now let's assume that the name of B is in one of the boxes 1..50. The probability of this happening is 49/99, since we know A is in 1..50 for sure. Under that assumption, the probability that B finds his name is N/50.
Assuming the name of B is in one of the boxes 51..100 (probability 50/99), the probability that B finds his name is (50-N)/50.

Thus, the total probability of B finding his name is:
49/99 * N/50 + 50/99 * (50-N)/50
That simplifies to 50/99 - N/(99*50).

N can be from 0 to 50, so the probability that B succeeds lies between 49/99 and 50/99. Multiply that with the 1/2 probability of A succeeding, and you're already below 30% for every strategy that B can possibly choose, and that's assuming the other 98 prisoners have a perfect strategy available.

In those cases that the strategy fails the prisoners, it is guaranteed that more than half of them will fail to find their name.

An independent observer, aware of the distribution of the names over the boxes and of the strategy of the prisoners, can predict perfectly which prisoners will fail, and which will succeed.

There is a small but significant chance of ~1%, using this strategy, that all prisoners will fail to find their name.

AFAIK, the surprise test paradox is unsolved?

After Bill ruled out all days, he assumes that the teacher can't be telling the truth. Next week, there is a test on Tuesday, and Bill is very surprised

I think calling it unsolved is a bit strong. Although the wikipedia page seems to indicate many schools of thought, here is my attempted analysis:

The induction over the days of the week is a red herring. The real issue is a construction sort of like the liar paradox, but predicated on the student's knowledge, so that the paradox only applies for the student and not for the teacher or an outside observer.

This becomes more evident when there is only a single day, rather than a week.

That is, the teacher says
(1) We are going to have a test tomorrow.
(2) But today, you do not/will not know that we will have a test tomorrow.

This boils down to
(1): TeacherTruthful -> Test
(2): TeacherTruthful -> not Knows(Test)

We interpret "Knows" to mean "student can consistently deduce", and from the student's perspective alone, this boils down to the axiom Knows(x) <-> x. Let's say the student can apply this axiom but he cannot in general decide the specific truth value of Knows(x) for arbitrary x because he cannot simulate a copy of himself to determine whether he would ultimately ever be able to deduce x.

What is the poor student able to conclude here? From the student's perspective:

Assume TeacherTruthful. Then, Test and not Knows(Test). By axiom, Knows(Test) <-> Test. Hence, Test and not Test. Contradiction. Therefore, not TeacherTruthful.

Yet, we as outside observers can prove (with some work) that the student, continuing from the assumption "not TeacherTruthful", will never be able to consistently deduce Test. Indeed, intuitively he has no reason to believe so, because he thinks the teacher is lying. Therefore, as outside observers, we know that "not Knows(Test)" is true. Therefore, if the teacher actually decides to have a test, then everything works out. It is consistent (from our outside perspective) that Test and not Knows(Test) and TeacherTruthful, but the student can never know this.

We can in fact simplify further. Consider the statement "This statement is true but you cannot consistently deduce this fact". Indeed, you cannot consistently deduce this fact, because any deduction of truth from you is contradictory. So, it is consistent that the statement is true. But you just can't know it without being inconsistent. It's actually the same thing as Godel's second incompleteness theorem.

For N = 4, 6, or 8 (instead of 100) the first N/2 prisoners should open the first N/2 boxes; the second half of the prisoners open the rest of the boxes.

For N=4, the prisoners survive ~16% of the time, for N=6 it's ~3.3% of the time, for N=8 it's ~1.4%. I will let it do N=10 here in a minute but I expect that to take a while.

EDIT: corrected n=6 above. Also, I realized I didn't let N=8 run to completion, there are ~37771564359352320000000 combination so that won't be happening any time soon. It happens that (what I believe to be) the best case gets examined almost immediately, so I believe the number above is correct anyway.

The teacher is lying.

But that does not mean that the teacher is not telling the truth.