Hmm, I am not sure if that is a windows media player issue. I have a TV card that I use to watch TV on my computer and although I use full screen mode (granted this is not through win media player) the following sometimes happens: A certain show or movie is widescreen, but only uses up a portion of my 20" widescreen acer monitor. There will be about an inch and a half border on every side that is not used. Then, a comercial comes, and the whole screen is automatically used.
So, I don't know if certain file formats or resolutions affect that or if that really relates to your case, but for starters, I would try playing a certain file with win media player and then with for example divx player to see if it is only the winmp that does not use the full screen. As far as I know there is nothing you can change in win media player once it is in full screen mode but for some reason doesn't use the full screen.