A longer interval than 10 minutes would be appropriate for BitDNS.
So far in this discussion there's already a lot of housekeeping data required. It will be much easier if you can freely use all the space you need without worrying about paying fees for expensive space in Bitcoin's chain. Some transactions:
Changing the IP record.
Name change. A domain object could entitle you to one domain, and you could change it at will to any name that isn't taken. This would encourage users to free up names they don't want anymore. Generated domains start out blank and the miner sells it to someone who changes it to what they want.
Renewal. Could be free, or maybe require consuming another domain object to renew. In that case, domain objects (domaincoins?) could represent the right to own a domain for a year. The spent fee goes to the miners in the next block fee.