It seems that Github runners use the hostname as runner --name by default. This lead to runner instances not being able to register for us, because AWS was re-using internal IP addresses.
Setting runner --name explicitly to a unique value should fix this.