So I realized I had over-complicated things waaaay more than needed. I took a peak at the Quake 3 source code, to see how they dealt with bursts of packets, de-synced time, etc. and the basic algorithm is this:

1. On every incoming packet read out the remote tick (or time)

2. Compare the remote tick with our own local tick

3. If they are close, do nothing.

4. If they are tiny bit to far apart slightly nudge our local tick in the right direction

5. If they are very far apart, reset our local tick to the remote tick .

I implemented this myself, in < 5 minutes, and it seems to be working wonders, and handle all cases very well.

The end result is this, straight copy-past from my game:

• RemoteSendRate is the send rate of the other end of the connection, in ticks.

    void IFpsAppTick.Invoke () {
        if (packetsReceived > 0) {
            Tick += 1;

            if (buffer.Count > 0) {

                // our goal is to stay (RemoteSendRate * 2)
                // behind the last received packages tick number

                int diff = buffer.Last.Tick - Tick;

                if (diff >= (RemoteSendRate * 3)) {

                    // If we are 3 or more packets behind
                    // Increment our local tick, at most (RemoteSendRate * 2) extra ticks

                    int incr = Math.Min(diff - (RemoteSendRate * 2), (RemoteSendRate * 2));
                    Tick += incr;

                    FpsLog.Info("Incremented TICK by +{0}", incr);

                } else if (diff >= 0 && diff < RemoteSendRate) {

                    // If we have drifted slightly closer to being ahead
                    // Stall one tick, by decrementing the tick counter

                    Tick -= 1;
                    FpsLog.Info("Stalling TICK at {0}", Tick);

                } else if (diff < 0) {

                    // if we are ahead of the remote tick
                    // we need to step back in time

                    if (Math.Abs(diff) <= (RemoteSendRate * 2)) {

                        // slightly ahead (two packets or less), 
                        // step one packet wort of ticks closer

                        Tick -= RemoteSendRate;
                        FpsLog.Info("Decremented TICK by -{0}", RemoteSendRate);

                    } else {

                        // if we are way of, just reset completely
                        // and start over, there is no point in trying 
                        // to handle this case nicely

                        Tick = buffer.Last.Tick - (RemoteSendRate * 2);
                        FpsLog.Info("Reset TICK to {0}", Tick);
                    }
                }
            }
        }
    }