If real-time streaming is done using FrameGrabber.grabAtFrameRate(),
this completely breaks the ability to seek on the grabber using FrameGrabber.setTimestamp().

This is probably because of the Method FrameGrabber.waitForTimestamp():

public boolean waitForTimestamp(Frame frame) throws InterruptedException {
        if (startTime == 0) {
            startTime = System.nanoTime() / 1000 - frame.timestamp;
        } else {
            long delay = frame.timestamp - (System.nanoTime() / 1000 - startTime);
            if (delay > 0) {
                Thread.sleep(delay / 1000, (int)(delay % 1000) * 1000);
                return true;
            }
        }
        return false;
    }

As you can see, this method delays the grabbing by calculating a delay with the System.nanoTime() and the frame.timestamp
But when we seek the video, frame.timestamp changes non-monotonically possibly causing this whole logic to break down.

I still haven't got my head around all this. But in my experiments, the grabber quickly grabs without any delay until we catch up with the current system time. And then keeps grabbing at the framerate typically.