Vmware Server on Linux supports setting virtual machines to power on at boot. From server console, Go VM properties :: Options Tab :: Startup/Shutdown , and the On Host Startup to Power on the Virtual Machine. I would imagine this can be done with other vmware software as well.
EDIT: Ah well to try to actually answer your question then:-)
When I run vmrun on my own box it doesn't ask me for a password. Maybe it only asks you for a password if you are using vmrun with the host argument (or if you need root privileges?) If this is the case, what about setting up password-less ssh using keys? Then you could just do something like ssh fooUser@myServer 'vmrun start /foo/bar/baz.vm' and that might work. If it does require higher privileges, you can give specific users permission to run specific commands with sudo and the /etc/sudoers file.
With Nagios monitoring, you can set up event handlers that will run a script (such as the command I posted) if it detects that the host in question is in fact down.