To be clearer, a trivial lower bound is something like "the input is of size n and for any n-1 length yes-instance you can find n-length extensions that are no-

To be clearer, a trivial lower bound is something like "the input is of size n and for any n-1 length yes-instance you can find n-length extensions that are no-instances, so you have to check all n elements." It doesn't tell us anything interesting about the worst-case problem complexity. What's been surprising is how hard it is to make meaningful lower-bound statements stronger than that (well, not surprising to people who work on this stuff for a living, I guess). But that doesn't make it more likely that P = NP, really, except in the sense that we (obviously) haven't characterized the entire space of problems in P yet. To more specifically address your "in-place" concerns, you can often formulate the problem in terms of circuit complexity--circuits are inherently parallel, so minimum circuit depth is a good proxy for a required number of steps, and it's also generally agreed that if you can design a circuit to do something it's physically realizable (even though that's arguably not always true, especially in cases with very wide fanout). So a (somewhat) promising direction has been to try to find circuit complexity lower bounds for problems, especially nontrivial ones.