I've seen one paper that says finding string theory vacua with particular low-energy properties is totally intractable, from a computational complexity standpoint. I've also seen people saying that they have figured out how to compactify the extra dimensions such that at low energies a SUSY standard model emerges. What's the truth about string phenomenology? Are we regularly finding new vacuua that look like our universe? Have we only ever found one? Any? How hard is it?
First, the entire subject of string phenomenology is not reduced to search by brute force for some internal space that produces a low energy spectrum that reproduces the SM one. See life at the interface between string theory and particle physics for an excellent (and conceptual) string phenomenology overview.
Are we regularly finding new vacuua that look like our universe? Yes. See A Quadrillion Standard Models from F-theory for a quadrillion of examples, an this nice blog post for divulgative information.
How hard is it? Its pretty hard. A navie argument that exhibits why is so hard to find new Calabi-Yau spaces, let alone one with semi-realistic properties, would be to recognize that that the typical number of moduli of a Calabi-Yau space is huge (sometimes of the order of hundreds), and those fields are subject to very few restrictions; then the expectation to write new CY metrics in an explicit way is hopless.
For a clear argument about the computational complexity of finding a particular compactification, with fluxes, and capable to produce a small cosmological constant in the Bousso-Polchinski scenario, see Computational complexity of the landscape.
Observation: The fact that a problem is $NP$-complete does not imply that we can not use other computational techniques, equipped with a set of reasonable assumptions, to give some special answers to this problem in a reasonable time. See Deep learning the landscape for an example of this.
Update: A nice paper on neural networks approximating Calabi-Yau metrics Neural Network Approximations for Calabi-Yau Metrics.