This is likely only tangentially related to your problem, but for the sake of creating a tutorial video in a given resolution, I needed fullscreen mode with a fixed size of 1280×720. Unable to find anything in Evince's command line arguments and options that would have helped, in the end I turned to running an Xnest server with the given resolution and started Evince inside.
I experienced exactly the problem you described. In my case, the culprit was that Evince started with its (X server given?) default window size and had no window manager available to tell it what size it actually wanted to be at. Starting xfwm4 in that artificial Xnest server helped: now Evince could ask to go fullscreen.
What does this imply for your problem? Not much likely, except that the configuration of your window manager is likely the best place to be looking for with regard to why the window resizing in presentation mode goes wrong, or even does nothing at all. And it might be worth trying out a different window manager (if necessary, by using a different desktop environment). If all else fails, using Xnest may work in the context of "screen" sharing though it would help more with specific application problems rather than, say, finding the best way to do something using your standard desktop.
