Yeah, but chain operations become extremely expensive over time. 

> If all I have is a pubkey, how do I find the corresponding IP?

There are many ways, but you basically would have a boostrap IP that can download NIP-65-like events of other relays. We could even use WoT to ask your friend's client to become the Bootstrap relay. Once you have a list of available options saved locally, you can easily get updated records by just querying a few of them. And if they go offline, you update the list with new ones. As long as you know the IP of a single relay, you can get all the others. 

 Do you think there’s any future for a decentralized dns-like protocol for unique vanity names? 

 I am sure brands love this. So, I am sure it will be there in some form.