That might be a bug with vino not working properly, Not always displaying. I expect it is probably only showing when a connection is initiated. After which it will continue to display. So it will initialize itself after it is connected to the first time.
You were almost correct it should have been set to "never". I just tested it on 10.04 LTS. I used the gui tool and checked to see what chanages it made to gconfig. The gconf-editor had this to say about it.
Long description: This key controls the behavior of the status icon. There are three options: "always" - The icon will be always there; "client" - You will see the icon only when there is someone connected, this is the default behavior; "never" - Never shows the icon.
To get it to do what you want I would use the never option.
$ gconftool --set /desktop/gnome/remote_access/icon_visibility --type string "never"
Check your setting is correct you should get out the value you set.
$ gconftool -g /desktop/gnome/remote_access/icon_visibility
That is the simplest way to stop people using the icon and getting to the preferences dialog. You would have to rewrite the icon widget they are using and recompile it to disable options it provides. If you are up for the browse the vino source.