Rackspace recently mentioned having tens of thousands of hosts managed with Ansible actually, and it works fine over SSH. Here's some slides on issues they ran into and resolved: http://prezi.com/tyasc3-vj_id/ansible-turbo/

Though one of the core technology decisions behind Ansible is that you don't need much to get it running. You can scale things up as needed, such as fireball mode. And you can boot strap that process using Ansible. You don't even need DNS.

Hosts can register back with Ansible on start up, this works today with their AWX product and cloud-init's phone home feature. Also your inventory of hosts can simply be queried from sources, such as AWS's inventory list, so in that case you can't have a host that's unaccounted for.