I've had the same scaling problem since recently upgrading my MBP 13in early 2011 to 10.7.5.
My setup is simpler with the target computer on my home LAN as a Windows Ultimate PC using UltraVNC server. I get the same scaling issue as posted in your picture. It was working fine prior to the latest MacOS update.
(seems like it's the month for Apple to be releasing sub-par software updates if you include iOS6! S.J. must be rolling in his grave!)
I have tried several other VNC servers on the target PC (as well as other target PCs) all with the same result, so my conclusion is the same as yours, it is something to do with the new version of Screen Sharing.
I have found however, that if you just try to resize the window slightly, then it will redraw the remote display to fill the whole window again. It's really annoying to have to do this each time though.
In addition, I have also found that the connection is a little bit more unstable - seeming to freeze suddenly requiring me to restart Screen Sharing. This didn't seem to happen prior to update for me. I don't think it's my network either as I haven't changed the configuration at all (target PC is on ethernet, MBP wi-fi).
Anyone with a fix would be greatly appreciated.
Thanks, it feels less lonely now, at least!
Your workaround of resizing the screen works for me, although it goes back to ab-normal when I switch to full screen. Very annoying...
I also had a couple of freezes so it really seems the same issue.
I tried several workarounds and ARD setup tricks found in this forum with no success.
For the moment I unhappily switched to tightVNC which works OK but is not as nice as screen sharing used to be. Other VNC viewers (JollyFast / cotVNC) seem to provide no scaling or very ugly aliasing....