Evolution wasn't trying very hard to create intelligence; it's really not that useful for survival relative to how expensive it is biologically, to the extent that some people think it's more an artifact of human mate selection and signaling (like a peacock's tail) than a proper adaptive trait.

Without a strong survival gradient pushing a population towards higher intelligence, it's actually surprising that evolution stumbled on it at all, which speaks to how easy it must be to find in solution space, not how hard.

I would be very surprised if a human-guided search can't crack the problem relatively soon - we're only just now starting to hit the threshold of computing power necessary to do it, so it's not too shocking that we haven't fully succeeded yet.