We're happily using a combination of Vine Server for OSX and JollyFastVNC for the clients.
Vine Server provides for a "personal" VNC server instance on a unique port number for each logged in user. The only trick is that the user needs to be already logged into the Mac with VineServer running under their account to be able to VNC in. The solution for the bootstrap problem this introduces is the Vine Server "System Server" that provides a VNC session for the Mac console - and thus, let's any user with access the console session log themselves into the Mac (and thus, start their own private Vine Server instance)
Configuration is relatively easy:
1/ Turn on Fast User Switching so that multiple users can share the Mac.
2/ Log in on the actual Mac console as an admin user that you also want to grant remote access to. Launch Vine Server as that user, and check the "Open at Login" preference.
3/ Open Vine Server Preferences and note the port number assigned to this VNC server instance. Manually re-enter that number to "pin" this instance to that port for subsequent launches. Also recommend that you set the password here for this unique user session.
4/ Go to the Sharing tab and make sure you check "Allow multiple user sessions"
5/ Go to the Startup tab and check the "System Server..." button. Start the system server instance on the default port (5900). This will be your console VNC server to use. (I recommend that you set a password on this)
6/ Close the preferences window and click Restart Server button.
You should now be able to log into two VNC user sessions: one as the Console on port 5900 and one as the admin user you just logged in as.
Now, for each user, have them log in and add Vine Server to their dock and repeat steps 2, 3 and 4 above.
The only two issues we've noted with this are that, if the Mac is power cycled, the System Server won't start automatically. An initial user needs to log in and start it via the UI.
The second issue is that if a user logs in via the remote VNC Console session, their subsequent use of the Mac will be visible in both the console session and their "personal" VNC session. i.e. the console session remains bound to the last logged in user until someone else logs in either remotely or locally. We work around this by opening the remote console session again after logging in and using fast-user switching to "show login window" which seems to force the console session to dissociate again.
JollyFastVNC enter the picture as a bonjour-aware VNC client with a nice "available servers" browser. This offers up the remote Mac "hostname:port" for each running Vine Server instance and the console instance, allowing easy navigation if you can't recall your port numbers.
Hope this helps.