If you integrate with a third party service and their environment is slow, because it's not a production environment, your tests will fail due to timeouts. How would you fix this?

One way I would think is to not go against their service; create a similar service and run it according to your SLA. But then, you have to make sure contracts are in sync, so you need to verify contracts from time to time.