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.

 

Good input, but my graphics control panel doesn't have graphic scaling options. But I'm carefully tinkering with the options that I do have, I'll update if I figure anything out.
When I set my screen to 800X600, it just makes my desktop have the same effect as the game... focused on the center of the screen. Which is also weird. Isn't it supposed to just stretch everything edge to edge and make everything bigger? That's how it worked on every other computer that I've had lol

Either way, thank you for the tips :>