I work on search and indexing systems at Google, and have done for more than a decade. I'm by no means the best, nor an authority. But I have spent some time living in this problem space, and this is my conclusion from my years of experience.
FWIW a single run of the tests for the system I work on now takes . . . I don't know. I would guess hours or maybe even a day of computer time? But, computers are cheap, and defects are expensive. So you split the test suite into bits small enough that the whole thing runs in ten minutes, and run them all in parallel. And, yes, there have been cases where I have had to debug the slow startup of a dependency so that I can make it fast enough to run in my test. But, that's what they pay me for, I enjoy that type of work, and it has ancillary benefits to the dependency when it needs to start up in production.
OK, well I guess this would be another caveat for my advice. If bringing up a production simulacra would take more resources than you have, then you might have to lean more on various types of doubles. This may be more often in environments that have insane prioritization of dev time vs. machine resources.
If I may ask, what was the bottleneck in your test suite? Did it saturate the cpu, ram, disk?