In my experience even getting all the pieces installed in a testing environment is hard. Specially when you need to make sure that they are all wired correctly, with the correct version, with all their dependencies (maybe different kind of databases, queues, caching layers) and on top of that if services are written in different languages, that adds another level of complexity.
Eventually when the system grows big enough and the team of people that needs a stable test environment grows big enough, it just becomes too expensive.
We actually use syslog-ng + Loggly for distributed Loggly. We partially solve the transaction problem by slapping a request ID on every action that's initiated by a web request. We then carry this request ID from service to service, which gives us the ability to trace exceptions cross-service. It's obviously not the perfect solution, but it has helped us many times when debugging customer-facing 500 exceptions.
We solved the service discovery problem by simply using DNS. Every service runs behind an (internal) Elastic Load Balancer, and we let the load balancer configuration figure out which instance is up and which one is down. Again, not the perfect solution, but it works great for now and is very easy to setup/maintain.