Triggering over-discharge protection will reduce battery lifetime
"[Overdischarge] protection is normally not used, i.e. it is allowed to […] [remain] outside the [usage] range for best lifetime. […] Do not use over discharge protection as signal for when to charge batteries, it might wear the batteries down faster." (source)
Maybe this answers your question already: discharging until over-discharge protection kicks in will wear a battery faster and reduce its lifetime. It will not outright damage it as you say, but reduce its lifetime, and should not happen during regular use. The device itself should also measure the discharge voltage and shut off earlier than the over-discharge protecting circuit, namely at 2.5–3.0 V measured under load, depending on battery chemistry (source).
This is called "minimum voltage for terminating discharge".
Is 2.5 V too low as over-discharge cut-off?
2.5 V as a cut-off limit for an over-discharge protection circuit is not "way too low", for the following reason:
The voltage measured by this circuit is measured during discharge (that is, under load), while the lowest voltage for safe recharging that you have in mind is measured as open circuit voltage (that is, under no load). For a lithium-ion cell, the two ways of measuring voltage will differ by up to 1.2 V due to the rebound effect. It depends on the load applied (higher load leads to higher rebound afterwards) and on the chemistry, age, temperature and manufacturer of the cell.
An example of the rebound effect can be seen in the following diagram (sourced from here), where a cell was discharged to 2.5 V at a load of 2.0 A, and then discharging was stopped:
The correct voltage at which over-discharge protection should kick in at latest depends on battery chemistry, manufacturer and load, but is typically 2.3-2.5 V for low-current applications (0.5-1C) and 2.0 V for high-current applications (assuming suitable cells, of course). (source)
What voltage will damage the cell?
You mention "Lithium batteries […] can only be brought to [certainly no lower than 3.0V] before risking damage to the cell". We already established that 3.0 V is the voltage under load at which discharging should stop to maintain the maximum lifetime of the cell. But discharging further will not immediately damage the cell, or make it unsafe to use.
So for completeness, let's see what voltage will actually damage the cell.
After cut-off by the over-discharge protection circuit and waiting for about one hour, we can then measure the open-circuit voltage of the cell. This voltage is relevant for deciding if it is still safe to recharge the cell. It is hardly ever stated explicitly that this has to be measured as open-circuit voltage, but (1) this is just how you measure cells in storage, (2) if it would not be an open-circuit voltage then the load to measure at would have to be given as well. Plus, (3) the following source implies that it is open circuit voltage by mentioning "dwelling" at that voltage, which does not happen if it were a voltage under load:
"Do not boost lithium-based batteries back to life that have dwelled below 1.5V/cell for a week or longer." (source)
Typically, a lithium-ion cell will not become permanently damaged or unsafe to use until its open-circuit voltage falls below 2.0 V:
"Do not charge batteries measuring below 2 volt, except if you have data [sheets] saying it is safe." (source)
So the 1.5 V limit mentioned above is not applicable always, but it (and sometimes even lower limits down to 1.0 V) can be applicable for some batteries of some manufacturers. Below that voltage, permanent damage to the cell occurs by chemistry degradation and copper dendrite growth. The dendrite can cause internal short-circuiting and battery fires during a future recharge and are the reason why a cell that has been discharged too low must be discarded.
Also note that any over-discharged lithium-ion cell must not be charged at full current but rather must be pre-charged at low currents with a special charger ("boost mode") until it reaches 3.0 V open-circuit voltage or more precisely, until an appropriate over-discharge protection circuit disengages. Most chargers of consumer devices cannot do this and will consider the battery "defective", but the cells are not actually damaged and can still be recharged safely when applying a pre-charging step as described.
For details about all of this, see here and here.