In my theory computation class, I was told that early computer pioneers didn't realize that some problems are intrinsically hard—what we now call NP-hard problems. Instead, it took a while to realize that some problems could be solved with better programming, and others... well, they couldn't.
For example, early sort programs were relatively slow, because they were limited by both available memory and algorithmic issues. I read the sort algorithm for the Univac and it's a merge-sort algorithm that uses multiple tape drives to sort more data than will fit in the computer's memory. As memories got larger, merge sort and heapsort became dominant. Then Hoare invented Quicksort in 1959, and people were really surprised, both because of its elegance and its efficiency.
Other problems didn't get a fantastic speedup—for example, scheduling. We now know that many of these are NP-complete, and possibly even harder than NP-hard. (PSPACE problems might be harder than NP problems, but then again, they might not be.)
My understanding is that NP-hard predates NP-complete, and I recently found this lovely article by Johnson, "A Brief History of NP-Completeness 1954-2012", which traces the history of the concept.
What I would like to know is when people working in the field did realize that some problems were intrinsically hard and that they weren't going to get dramatically faster solutions with simply more clever programming (absent a significant mathematical breakthrough). After all, linear programming was invented in World War II, and so with that, my guess is that many problems that seemed hard also seemed solvable. So, when did people discover that some problems are not?