I came to a situation very similar to yours from the Marine Corps.
There are two of us in the IT section and we have ~50 users. There were zero user policies, password policies, etc. We don't have Exchange and our ISP's web mail is not user-friendly, so we had lots of our sales team using Hotmail, AOL, etc. After instituting SurfControl (a web-monitor/filter) we discovered some users visiting literally a HUNDRED porn sites before noon.
This was a MAJOR culture shock for me. Coming from the Marine Corps I was used to signing my life away before I could even log on to a computer.
First and foremost, people need to realize that the computers they use on a daily basis belong to the company and as such, NOTHING they do on that computer can be considered private. People don't have to like it, but it is a necessary evil for legal and security purposes. Help them understand this.
I can think of a few things that might set your users' minds at ease.
(1) Include VNC in your user policies. Clearly state in the policy that IT will attempt to notify the user prior to accessing their computer via VNC. This way, they have a legitimate complaint to take to HR if IT often "pops on" their computer with no prior notice.
(2) We use RealVNC (not sure how similar the two are) and with RealVNC, you can choose to have the desktop background disappear when it is being remotely accessed. This is one way to notify the user.
(3) With RealVNC, there is a VNC icon in the system tray. When someone is remotel accessing your computer this icon turns black.
Personally, I wouldn't use the query method. VNC is about convenience and believe me, that would be decidedly inconvenient.
Educate your users about why it is necessary and put it in writing that you will only access their computer after attempting to notify them first. They will become believers the first time you fix their problem in a matter of seconds (as opposed to waiting until you can make it to their desk) thanks to VNC.
