Version:            (using KDE 4.4.1)
Compiler:          gcc 4.3.4 (x86_64) CFLAGS="-march=native -O2 -pipe"
OS:                Linux
Installed from:    Gentoo Packages

I opened the 2-page pdf at
http://www.subaru.com/content/downloads/pdf/maintsched/2003SchedFed.pdf
using okular within konqueror, using the right half of the screen at 1920x1080... exact pixel counts should be visible in my screenshot here (showing the with-scrollbar state):
http://www.polypux.org/pictures/sskdebug1.png

Basically, when the scroll bar is present, the width of the page decreases, and the height of the page decreases so that the whole thing is visible... which means that the scroll bar goes away, and the width increases... so the page bottom goes below the bottom of the page, and it requires a scroll bar. Rinse and repeat.

The problem with this bug is that it only shows up on particularly bad combinations of pdf's and window sizes, and that there is no obvious (to me) solution - the oscillation should be stopped, but having the scroll bar is ugly when not necessary, and you need it... maybe some system by which the page makes itself slightly smaller to avoid this?