Using Debian "unstable" on 2.6.8.1, under KDE.

2 screen setup with left screen at max resolution 1280 x 1024, right screen max resolution 1024x768. Playing a video using Mplayer, when I run fullscreen, the picture sizes correctly on the left (primary) display, but if I move the window to the right screen and fullsize it, it assumes the complete right screen but part of the picture on the right side is cut off. I'm not sure if this is an issue with MPlayer, X (xinerama) or ????

I think this is a limitation of Xinerama, or maybe your WM. The window manager cannot get its head around the fact that your right-head is smaller than your left, so it is assuming that your right side is the same size. Thus it is displaying your movie "fullscreen" at 1280 x 1024 even though the display is only 1024x768.

This is what is known as dead areas, screen real estate that doesn't exist although the WM thinks it does.

I am not sure how to get around this. Do all apps have this behavior? ie: when maximizing a browser window or anything else?

This only appears to be a problem with MPlayer, and even then, only with the fullscreen video. Any application windows (including MPlayer windows), when maximized in either screen, assume the correct dimensions taking up that whole screen with no dead areas.