No, this is a pipe dream. The only valid state for a sorted list is sorted. You can not possibly "test for invalid state" here because there's no way you can handle a sorted list that is not sorted in any meaningful way.
Mind you this example is the one of the most trivial data structures in existence. Real software has insanely more complicated valid/invalid state, the size of the state space growing exponentially with the number of components.
If I have a method wrapped around adding items to a list, then I'd call that method with random data. Then, I'd call the method that gets the items from the list and I'd check that the order is consistent. Now, you're testing that the underlying implementation is a sorted list.
I'm sure you can object in many specific cases, but the point is there's no general way to do that. Even your description could be unable to find the famous Java bug with integer overflow in binary search had it only happen on extreme cases. I'm not even talking about race conditions.
And these are still single components, so the exponential growth of state combinations point is left unaddressed. In fact, it directly supersedes your point in this comment, as the exponentiality eats your "random data" idea before you even wrote it.
We're not testing Java, we're testing your code which is a method to add items to a list. If it passes the tests, great. If there is a bug in the JVM, maybe it picks it up or doesn't. That doesn't negate the need for the test.
The way I look at testing is less about the current point in time. It is about changes over time. If someone else comes along and changes the underlying implementation to a list where sort order is not guaranteed (maybe thinking their version is faster or something), then the tests will fail and that's exactly what you want. You're testing the expected behavior over time and right now, the expected behavior is a sorted list.
Regardless, I don't understand what you're trying to argue or prove here. Yes, testing is hard and not easily won, I already said that.
"Of course, it helped that long ago I had put in all of the legwork to have near 100% test coverage, so I could be certain that the migration did not introduce any bugs."
You can try to avoid it by architecture or abstractions, but it only works to some extent.