I also agree that the "real world" does this some times, but there is a difference between writing simulations of the real world and writing programs. I'm not disturbed by the idea of objects encapsulating hidden state, but rather the idea that objects have static, invariant interfaces.
One of the nicer ideas for dealing with this is to write explicit state machines and where (if your language allows) the interface actually changes as the state changes. If o.a(); o.b(); is different than o.b(); o.a();, you can write a state machine that makes this inspectable and explicit. If o.b() makes no sense until you call o.a(), you can simply not have o.b() be part of o's API/interface until you call o.a().
I won't suggest this is a general programming heuristic, but my experience in the last couple of years is that every business object modeling a real-world business entity ought to be implemented as a state machine until you discover a compelling reason to do something else. Ad-hoc state machines, like having the logic for whether o.b() does x or y based on the contents of fields _a and _b be embedded in the method b() are the stateful equivalent of spaghetti-coding with GOTO.
I credit Pete Forde for shaking me out of the complacent belief that I'm smart enough to embed everything in methods.