Rendering Glitch

Settings:
VBO: Off (Surprisingly, turning VBO On removes the glitch)
Rendering Distance: 20+ (Not happening in rendering distance lower than 20)
Mipmap: 4 (Don't know if this matters)

It happens every time when I play the world.
I've tried restarting Minecraft, restarting the laptop, and also tried re-installing the graphics driver. None of them helped. I've recorded a video so you could see what's happening.

http://youtu.be/5DtiDQi_AYo