Windows XP/Vista/7 Very weird full screen problem

So... I've been playing in windowed mode because I have to. I don't want to, but I have to because my fullscreen mode has the following characteristics=

The actual game itself is the same size as windowed mode, placed in the middle of the screen, surrounded in black. I would post a screenshot, but I am unable to for some reason. But to clarify, there is black on top, bottom, and both sides. and then the little bitty game in the middle. So that's one thing.

The other thing.... when I try to play the game like that, in full screen, there is lag. Not internet lag, but keyboard lag. For example, I press and hold an arrow key to walk, let go, and my character just keeps moving for a good few seconds.

Info=
Win7 Ultimate
GPU=ATI Radeon x1200 Series (laptop graphics)
CPU= AMD Athlon 64 Bit Duel Core TK-55 (1.8ghz)
Screen= laptop screen
RAM= only 2 gigs :<

Graphics driver is completely updated and appropriate


Oh, and I tried running Legends on my girlfriend's laptop, which is literally identical. They were bought as a pair. Same problem XD

So... any ideas lol I don't even know where to start, but I'm kinda sick of windowed mode on this tiny as screen.