yes, it is definitely possible - like I say, I'm doing it and it works fine ... I've tested for you again today, connecting to the following:

windows 7 home premium (frigged to allow rdesktop host)
windosw 2003 server
windows 2000 server
and all open fine in fullscreen when called from within a script on my n900 (didn't test via an ssh but IMO that's irellevant to your issue).

note - running rdesktop -f connects fullscreen (with the fullscreen toggle icon in the bottom right of the screen) - if I toggle, the window is entitled rdesktop - xxx.xxx.xxx.xxx), but running rdesktop-cli -f does NOT result in fullscreen, I get the session displayed in a window titled "xterminal" and without the fullscreen toggle icon bottom right.

As I said previously my installed version of rdesktop is 1.7-maemo3 while rdesktop-cli is at 1.6.3-maemo3 (both according to FapMan).

However when I type rdesktop (no parameters) it reports client version 1.6.0, and running rdesktop-cli (no parameters) reports the same client version. rdesktop-cli is in /usr/bin, size 224472 bytes, while rdesktop is a symlink from /usr/bin -> /opt/maemo/usr/bin/rdesktop, size 250792 bytes.

It sounds to me like you may be running an old version of rdesktop (or maybe you've previously manually created a symlink to an old version or something)? I suggest you double check that you are up to date - uninstall & reinstall the app's if neccessary to be sure - and double check what is actually running when you call rdesktop.