E.g. MPEG4 videos are usually made of I-frames (full frames), P-frames (predictions based on older images) and B-frames (predictions based on older and future pictures), and from these Group Of Pictures are made, which always start with an I-frame.

You cannot make frame-precise cuts within this sequence unless you wish to carry on the frames that won't be visible (and I don't think anyone tries to do these cuts by keeping some invisible frames), so you only get to make such edits that always include the first I-frame of the sequence.

Therefore if you want to make completely lossless edits your editing precision is lost. For frame-precise editing one usually ends up re-encoding the stream.

Of course, you could only re-encode only the GoPs that get broken while keeping the rest intact, and I guess this would be better and a lot faster than re-encoding everything. I don't know if any application tries to do this. But that is also a bit troublesome, as you'd like to use the same encoding parameters—and maybe the same encoder—as the other frames, to not have quality differences between the edits and original.