After fiddling around with this irritating nonsense for a while, I came to know the real meaning of the full screen option in Remote Desktop settings.
Instead of the intuitive meaning of really full screen in the monitor you maximise on, it actually means “same resolution as my primary monitor”.
To get it to full screen on any screen, set it to start in windowed mode and then maximise it in the monitor you want.
This post has more details: http://www.codinghorror.com/blog/2006/04/remote-desktop-tips-and-tricks.html