It starts off by populating the key values as wildcards:
*.keya._domainkey.example.com TXT "v=aaaaaaaa" *.keyb._domainkey.example.com TXT "v=bbbbbbbb" etc
This mechanism does not require an excessive number of public key entries. It does enforce a per message lookup but that is inevitable in a scheme of this type.
There is a caching implication here of course, but we are talking about wildcard lookups here and DNS is already designed to deal with them and avoid bad caching.
-- William Leibzon Elan Networks william@xxxxxxxx