When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the route generation process. Are there computational (or numerical or mathematical) tricks to perform this constraint verification quickly for a given route (sequence of nodes)? In particular (and this is the harder case) when you can't wait until the time window starts (meaning, can't arrive way too early to a location).
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?