This is the difference between Key frames (or intra frames) and predicted frames (or inter frames). Different codecs put different emphasis on the different frame types. Ideally key frames will have the same quality as the other frames, but different codecs can put different emphasis on quality for the different frame types.
I haven't looked at Theora since it was known as VP3, but if I remember correctly, while most codecs' predicted frames can only draw from the immediately previous key or predicted frame, frames in VP3 can always draw from the previous key frame. This means that key frames are more significant to VP3 than MPEG-4, and might explain why they spend more bits encoding their key frames.

someone really should moderate down all of these achievement whores... like me...