You're right. Fortunately key frames tend to be pretty close together on the MPEG-2 streams in VOB containers.
Any free MPEG splitter/joiner can join the new VOB to the old VOBs.
Do you have an example of a good one that is free? I know that DVD2one works perfectly for joining VOB's. Come to think of it, the small, free general purpose utility called "FileMerger" can join VOB's, but it doesn't write out a corresponding IFO file of course; it is useful for joining multiple VOB's to be directly edited in VDubMod before making an AVI. That's what I like about DVD2one; it doesn't simply join VOB's, it writes out a new set of VOB's along with writing out a corresponding IFO file (the new information in the IFO's is what is really responsible for joining the files, as the resultant VOB's are still split into 1 GB chunks) and it is a ready to go DVD when it is done.