Unfortunately, the problem is not restricted to iTunes. I have the same issue with Front Row. I want to be able to watch full full-screen video, which I can with Quicktime (although a little quirky when watching videos with subtitles). My issue is, I like to watch several videos in a row, and with Quicktime every time a video ends, I have to go up to the computer and start the next one. With Front Row I can just use the remote, but then you have the black bars.
Now, I went over to Apple Discussions to look up this issue and apparently it's been a problem since 2008 for some people.
One "solution" is to change the resolution to 1024 x 768 (stretched) then play the video full screen, but to be honest, that's a compromise. Unfortunately, at this time your options are QT or VLC (if you need to do playlists).
Wish I could have found an answer for you since it bugs me as well.