Agent push is attempting to push multiple agents to the same EC2 instance, duplicating name and consuming licenses

We have a cloud profile set up with one of our AMIs, and our configuration leverages the agent push feature whenever a new EC2 instance is needed. We have no "always up" agents, all are spun up on demand when builds enter the queue.
Whenever a new EC2 instance is spun up to accommodate our builds, the agent is pushed to the EC2 instance with a name, e.g. EC2-XXX, and the server is notified that the agent will upgrade. After about 60 seconds, the server logs report that the EC2 isn't responding, and attempts to push the agent again, creating a new agent with a duplicate name, e.g. EC2-XXX-1, and the process repeats itself.
This always happens 2-3 times before the agent actually connects and starts executing jobs. The problem is that while agent with the name EC2-XXX-3 might be running the build, agents with names EC2-XXX, EC2-XXX-1, and EC2-XXX-2 are all still pending upgrade in a disconnected state. These agents never connect, preventing further instances from being spun up because they are consuming our licenses.
For example, from the Agents -> Disconnected tab:

In this scenario, agent with a name "EC2-i-017a69f1aa5dc36c4-2" is connected and running builds, but these 2 "fake" agents are sitting in the disconnected state consuming licenses.
Are we doing something wrong? We don't have any agent names specifically assigned as they are all spun up on demand from our cloud profile, so we allow the host name to be used.