I don’t think this is true. CREATE2 (from EIP 86), which will allow a new way of creating a contract using a user-provided salt rather than an incrementing nonce, should make it possible to set up a registry where the registry contract maintains no state. The registry contract would just create a new single-domain-management contract using sha3(domainName) as the salt. Then anyone could compute the address for the single-domain-management contract for any given domain name, without even needing to consult the registry contract (whose main responsibility is to create the single-domain-management contracts).
Also responding to something from the other thread:
I don’t think this is true either. You never have to grind to find a nonce; whoever is trying to prove the provenance of the contract would provide it to you. (Or if you insist, the contract could even keep track of the nonce of its parent at the time it was created, so the child contract’s state contains all the information necessary to validate its provenance.) CREATE2 adds additional possibilities here (every Cryptokitty could have a unique name, and sha3(name) could be the salt when its contract is created; this would let you look up any Cryptokitty contract on the blockchain, by name, even without a hint from the owner).