Rather than using a discovery server, couldn't you throw in the web3 library and use Ethereum for that purpose? You could keep the discovery server as backup for people not connected to Ethereum nodes, but for those that are you'd be fully decentralized. To keep things cheap you could use Ethereum's event logging rather than actually storing data on chain.
In any case, this is great, I've been looking for something like this.