I totally agree with you that storing every single deposit would be pretty gas inefficient and expensive.
While implementing a vested token for our project, we ran into the same difficulties.
We decided on using a curve to relate our network token to the vested token, taking the lockup duration into account. Vested tokens are minted at the time of the lockup, taking into account the full bonus.
We just deployed this relatively gas efficient token.
We are able to store the information in a single mapping of addresses to uint256, by encoding the endBlock of the lock, the total amount of locked tokens, and the total amount of tokens minted.
Lock times are averaged out if further tokens are locked. For our contract, we decided on providing a minimum and maximum lock duration and the user can decide completely individually for how long they want to lock.
Lock transfers are not implemented in our first version yet but would entail the lock duration to be affected similarly to locking more tokens in that the lock durations are averaged out.
In such a case, an exit would not be possible until the end of the lock duration, thereby achieving a removal of liquidity from the market.
Rewards will then be distributed among all holders of the vested token. If such a token concept or a similar one would make sense for xSushi, we would be thrilled to provide an implementation.