I'd have to get home and boot up Linux to try them out, but the ones coming to mind are Darwinia, Trine, and World of Goo. Is there a way that I, as a user, could manually set that fullscreen hint?

You could set the fullscreen hint yourself. The problem is that setting it on an override redirect window will do nothing, because override redirect exists solely for the purpose of telling the WM "Never touch this window." You would have to figure out how to make it use a regular window.

It's unfortunate. The mechanism to allow the WM to handle fullscreening intelligently is there, but it seems that the developers weren't aware of it.

Hmm, perhaps there could be another approach. Like lying to the certain applications about the resolution of the 'screen', to return the dimensions of the primary monitor, and then map coordinate 0,0 to the location we want the app to start at.