how do you handle service discovery in dynamic microservice environments?

Hey everyone, I'm working on a new microservices platform and we have services that start and stop all the time. It's a real pain trying to keep track of where everything is. We've checked out tools like Consul and Eureka, but I'm wondering what else people are doing. What do you all usually do to make sure services can find each other when things are changing so much? Did you run into any weird problems or learn any good lessons the tough way?