Newton's laws have never been overturned, merely refined, so we've never truly shifted away from a Newtonian paradigm.
A better example (and one that Kuhn himself used), would be phlogiston theory, which was fully overturned when oxygen was redefined as an element and not as simply being "dephlogisticated air".
Phlogiston theory was overturned but the idea of oxygen is still standing strong despite the major advances in chemistry since 1773. Other puzzle pieces have been placed around it but they're additions to it. Even if the universe turns out to be a hologram the idea of oxygen will survive.
Once the big puzzle pieces are found they're rarely removed. Since the big shift towards empiricism most "revolutions" and paradigm shifts are happening in new areas or at different scales than the old ones. Much of what are being called revolutions I would call explorations of the unknown.
To give an example, how much do you know about theories of geology before 1960? Any educated person today knows the basic idea of plate tectonics, but only a historian of science might know what came before.
According to Kuhn, the impression you get that "puzzle pieces are rarely removed" is something that happens after science has been rewritten to fit a new paradigm.
A quick visit to wikipedia shows modern geology dates itself back to the 17th century. You can view the field since then as successive additions and modifications to what was started by Nicholas Sterno in 1669 when he stated the law of superposition, the principle of original horizontality and the principle of lateral continuity. Those are 3 of the 7 principles of modern stratigraphy that wikipedia lists, but according to you and Kuhn the "modern paradigm" of geology starts in 1965 and everything before that's been erased?
I'm not here to argue with you in case you have that impression.
> "When we read a science textbook, all of the information is placed within the structure of the current paradigm, as if none other came before it."
Newtonian physics isn't taught from within the frameworks of quantum mechanics or relativity. The opposite is true, it's taught as if we live in a constant-time, deterministic universe. That's an exact wrong prediction for the most central and fundamental field of science. To make it worse it's something that's easy to check. That's frustrating.