"This is because each MP3 frame is not encoded independently of each other. "
Yes, this is the bit reservoir(sp?). It carries some info from frame to frame.
A patch was recently committed to fix --nogap in the most recent lame alpha builds. I'll give it a shot tomorrow and report on how it turns out with 2.0.