How can I automatically start VNC Server on a Mac to enable remote login after restart?

This has been driving me crazy since around when you posted this question originally. In case you never figured it out, or others find this post (it was the second result on Google for my search) I finally realized that my problem was having VNC Server in the User Login Items in System Preferences. Yep. See, when you launch RealVNC's VNC Server, it automatically starts as a Service -- which I finally realized means it launches automatically, *without* having to be in the Login Items list. So adding the app itself to Login Items specifically calls the details/options interface, which of course requires a password, because it's now a system level process! The problem is that doing so prevents the Service itself from loading. I hope this helps someone because it's been driving me crazy for literally years.

Great! How exactly do I do that?

Yes. Once installed it can be configured to always on, running in the background. Regardless of intentional or unintentional restart, the VNC server will be running once the computer is back online.