This is a normal message if Action verification fails.
Virtual Machine (and other) policies that start or stop an instance have a built-in verification feature that executes automatically after the policy is run.
After a Policy Action to start or stop an instance is run, the Policy engine waits a period of time (long enough to insure that the state of the instance has changed and that this change has been detected - 40 minutes by default). If the Action calls the provider API to start or stop an instance and that call is successful BUT the verification finds that the instance is not in the requested state then "Verification Complete. Virtual Machines not started" is displayed in the "Dashboard=>Notifications=>Actions->Failed Actions" view along with the ids of the instance or instances not started. The Policy Action status is recorded as either "Succeeded With Failures" or "Failed".
In this case please review the action in your cloud provider logs or consult with their support team for more information about why a requested VM was not started but the call to the API to start succeeded. Also verify if the instance state was changed after the time the Action was executed by some other tool, process, or person.