I have tried inputs in H.264, MJPEG and MPEG-2 (each completely different video) and with each one there was this problem, so I find it pretty suspicious.
Do you know about video with which faster preset outputs smaller file size than veryfast preset?