I understand what you are saying about not knowing the past from the current state because there are many previous states that could have lead to the same current state.
I remember being surprised when Leonard Susskind talked about even when you have an OR gate in a computer that outputs a yes, you would think that you don't know if you had a yes/no, yes/yes, or no/yes input after the input bits are erased (e.g. an electrical charge is changed) in the computer. Although that information can no longer be retrieve from the gates in the computer, it's erasing has affected the environment, and therefore it hasn't been lost, from his perspective. I'm not sure if this viewpoint, that information is never lost, is broadly accepted in the physics community or not.
In this OR gate situation(or any situation), I think Wolfram would say that the system has become a little more encrypted. So the passage of time is in essence a calculation that leads to more encryption... so the information isn't lost, but it would be very difficult to deduce what the state was before... Or actually maybe impossible if you consider yourself in the system. One thought is that in order to do the decryption calculation to figure out whether you had a yes/no, yes/yes, or no/yes situation, you would have to freeze the system, step outside the system, take a perfect account of every bit of information in the system without disturbing it (avoiding the uncertainty principle), do the calculation outside the system, and then pop back into the system to report your findings... which I don't think is really achievable for someone in the system... unless of course some of those spiritual, Ayahuasca trips to higher systems of consciousness are real. Maybe you and Paul could devise some new experiments? :) Just some thoughts... Do institutions give out psychedelic grant money? Hey, FQXi seems like a pretty open-minded institution;)
If any of these ideas have stimulated thoughts (or amused you), please check out my movie trailer if you get a chance:)
Jon
p.s. After using the hyper-linking syntax to link my trailer, I wondered what issues I'd have if the web link I embedded ended with "][/link ]"(less that extra space)... Could we create something in our universe that would hack the code that runs outside our own universe?!? Sorry to get all "digital physics" on your page here; A (wo)man's got to promote:)