Why do most battery protection circuits have 2.5V discharge cap?
This may not be a definitive answer, but a couple of points to note when choosing the threshold voltage.

The output voltage of a cell while discharging is lower than its quiescent voltage and the difference is higher for higher current. If you disconnect the cell after reaching the low voltage limit, its voltage will recover a bit. That's why discharge controllers should have hysteresis or memory to prevent them from turning on again without a charge cycle.

Another thing is if you look at a discharge curve of a Li-Ion battery, you will see that the voltage drops very quickly at the end of the discharge cycle. There is just little difference in terms of remaining state of charge between 2.5V and 3.0V. So the actual implication of choosing 2.5V vs 3.0V threshold voltage may not be as dramatic as it looks.

UPDATED. This document includes a discharge diagram: https://engineering.tamu.edu/media/4247819/ds-battery-panasonic-18650ncr.pdf.

At low current (0.2C), the difference in charge between 2.5V and 3V is ~3%, the cell is practically empty.
At higher currents (2C) the difference is higher, however, this is partially due to the discharging battery being "unable" to yield all stored energy quickly. In this case, voltage recovery will likely be more significant.

UPD2. Summarizing, to make my points a bit more clear:


When talking about voltage of a battery, it is important to distinguish quiescent voltage and voltage under load.
2.5V to 3.0V is a reasonable interval for shutoff voltage under load. 3.5 V is certainly too high. 


UPD3. By the way, all diagrams on the datasheet above are specified under V_cutoff = 2.5V, including the particularly interesting "Cycle Life Characteristics" one.