"[Apple's] problem is that they thought they did not have a problem." Crucial insight, there. From the perspective of an observer who has no special affection for Apple, it's surprising that a company of that competence would succumb to such a basic process error.
If there's one thing that Apple hates as much as a half-baked UX, it's dependency on another tech company. It seems pretty obvious to me as a casual developer and observer of Google maps over the years that global mapping is really really hard. How could Apple not have known this? I don't think even they have this much hubris.
Now we don't know why negotiations with Google for the maps API failed. Maybe Apple was overconfident, maybe Google was playing hard ball for Android's sake, maybe a bit of both. But regardless of the reason, the contract was not renewed and they had to release something. The iPhone without maps is not the iPhone.
The fact that they used an algorithmic approach to QA says more about the timelines than Apple's beliefs about the overall best approach. There was simply not time to get people on the ground to do a proper QA job. Apple's hands were tied.