I have had the same problem, and found that the only fix was what you last said, remove the beginning/end/both (random amount of frames it seems) from the timeline.
Then I would make new original captures of what I chopped out, and re-added them to the beginning/end/both.
Always worked for me - highly annoying tho.
My System Specs:
Cameras: 2 x Canon XL1s
Computer: Dual Intel Xeon 2.8Ghz processors (hyperthreaded) - Intel SE7505VB2 mother board - 2 Gb PC2100 RAM kingston -Adaptec FireConnect 4300 -2xseagate 10K scsi hdd 150G ea -2xseagate 7200 ide hdd 200G ea - Plextor PX-708A DVD burner - ATi Raedon 9800Pro video with Dual SUN 21\" monitors - Sound Blaster Platinum live!
Software: Windows XP Pro with SP2 - Pyro Pro (adobe\'s premier pro, encore DVD, and audition bundle)