I've checked my PAL KOF 2000/2001 disc and it has the same issue. The 50/60hz and game select menu's are fine, but when KOF 2000 starts (at 640x256) only the top 87.5% of the screen is used. KOF 2001 does not have this issue, but it runs at 640x448.
I've checked all settings(including trying the 50hz mode) and no changes.
Like nachash I've also tried an older version (pcsx2-v0.9.9-r4671) and can concur it appears on both old, new and stable releases.
Artifacts do occasionally appear on the bottom 12.5% on the screen like nachash's screenshot of the character screen.
Another screenshot of the bug:
[attachment=57731]
Fixed with temporary cheatengine hack to show it should look(value changes on every reboot):
[attachment=57732]
Hardware mode also shows some slight vertical lines on the characters, but haven't look into that any further yet.
I haven't tested this yet but something like this happens in Devil May Cry 3. If you select 60Hz output, the image gets squashed and you'll get a black horizontal bar on the bottom.