We've had a good deal of trouble configuring our Xserves so that various systems can reliably connect to them via VNC. One particular sore spot has been making the built-in screen sharing client on ordinary Snow Leopard connect. Is there a reliable recipe for this?
If you want reliable remote/VNC connection on OS X, just pay Apple for Apple Remote Desktop. It's not cheap, you shouldn't need it - but it is great to use and very reliable.
http://sourceforge.net/projects/osxvnc/ -- Use vine as the VNC server
http://sourceforge.net/projects/cotvnc/ -- Use CotVNC as the client.
This solution worked quite well for us when we were looking into various ways of being able to remotely access our OSX machines.
The other method would be to use http://www.logmein.com on the computers.