Funny you bring up CNC - OpenRA immediately came to mind for it's horrid pathfinding code that trips itself up when units start crossing bridges and things like that causing units to immediately reroute around the map instead of realizing that the bridge will clear since those units are in motion - red alert 2 at least dealt with this far better but I'm not where near smart enough to figure out how to write code to fix that type of problem.
If the graph is directly modified by dynamic obstacles, store "time to available" in the busy edges. Then the unit walking in can check if by the time it gets there, the edge is still busy.
If obstacles are handled separately, you do the same thing except it ends up being a line intersection between nearby agents' routes. Find route intersections, estimate arrival times, if they conflict based on both units' movement speed, reroute.
Another approach would be to ignore unit as obstacles and rely on movement timeout: If I'm stuck for longer than X time, reroute.
