Automatic power on after graceful shutdown on UPS

This is a case where you shouldn't be using two UPS units, where each feeds a power supply. That may be a big part of your problem, as a single UPS can restore the previous power state following an outage (this is the default in the HP ProLiant BIOS as well). Having two seems to mess up this logic.

Are you connected to the UPS via serial or USB cable?

See the specific suggestions at:
How to wake a server after UPS Shuts it down when Mains power is restored?

This should be easy to test, but to be honest, I spend very little time dealing with these edge cases. Server room power is one of the easiest things to plan for, in that you can spec x-hours of battery runtime and be able to ride through power-loss scenarios like this.

If the outages are longer, I just make sure I can remote in and handle things manually.

An alternative solution that requires no hardware change is to setup the shutdown process to reboot if the UPS has power after all the VMs have shutdown. This will involve figuring out where in the shutdown process you can put your init script and you need to make sure that nut doesn't get closed beforehand as you need it to communicate to your UPS.

Are you sending a shutdown command to the UPS at the end of the server shutdown? If not you could consider also the option to do that and then you can set the delay until shutdown so your server really finished the shutdown and also a timeout after the ups has gone down and until it powers up the server after power is back. If power is back before the shutdown completed you will still have your server powered down completely by the shutdown command but it will be brought back up after some timeout.

Check the NUT upscmd shutdown.return and the associated timeouts.

A ghetto solution, but it works. Get a small mikrotik router or a Linux board, and put wake on LAN in it. Place the device without ups backup, configure it to send wake on LAN every minute or 30 sec. So when it loses power, it sends no commands, but when it gets power it sends WOL every 1m or 30s. So your server never shuts down when power is on.