I know this was "fixed" a long time ago, and I can't find any other recent reports of it. But this weekend I installed PA for the first time on an HP Envy laptop (quad core i7, radeon 8750) and it just doesn't want to go full screen. I've tried all combinations of F5, alt+enter, and Window/Fullscreen mode in settings, and hitting the Maximize button. Once, by some miracle, when a game started it was fullscreen. But as soon as I switched out and back it had a border again. The border sometimes says "Planetary Annihilation" at the top and other times shows the menu bar of the last application, such as Firefox. It usually obscures the PA UI at the top, though sometimes the UI will shift down so it isn't obscured. What the hell could be going on here? Other fullscreen games work fine, so it's something about the way PA is going into fullscreen mode I guess...
Any chance you have effects (Windows Aero) disabled? If yes it's this task: PA#3230 I suppose it's going to be fixed if (when?) Windows version of PA will use SDL.