Even the A* search algorithm is technically AI.
At least that's what we used to do.
Btw, you bring up the perspective of realising that our tools weren't adequate. But it's broader: completely ignoring the tools, we also realise that eg being able to play eg chess really, really well didn't actually capture what we wanted to mean by 'intelligence'. Similar for other outcomes.