I refer to S/Kademlia's idea to define the number of consecutive 0s in front of the NodeID as difficulty and to impose a minimum limit on the difficulty of the NodeID allowed to be stored on the DHT. As the S/Kademlia paper said, they just use the PoW NodeID way to obviate Eclipse Attack(Make Kademlia Network Fork), Sybil Attack(Fake Nodes), Churn Attack(Frequently Join & Leave), Adversarial Routing(Spread Bad Route).

Adversarial Routing is a bit related to DOS Attack you described. As the DHT is a gossip protocol organized network, maybe some Peer Rating stuff with PoW NodeId will work out an intergalactic-internet scale DHT. Just a well behaved proper difficulty NodeID will be trusted to spread more NodeID routing info.