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.
The other method would be to use http://www.logmein.com on the computers.