Or formulated otherwise, looking backwards in time, we should expect to see an increased thermodynamic entropy. The paradoxical thing to me is that we seem to assume that in the past entropy was even smaller than today!
The following assumes that the description of microscopic motion of the particles of the system is Hamiltonian (your system qualifies for this).
I will use the word thermodynamics in its restricted sense, i.e. the subject treating effects of heat and work exchange between bodies on their states of thermodynamic equilibrium. 2nd law of thermodynamics talks about changes between equilibrium states only.
The impression of a paradox and disagreement about its importance, resolution and whether resolution was found persists for more than a century now. No doubt this is partially due to the fact people teach many misconceptions at universities and their students later publish some of them in their papers.
Here is one solution that is known at least since 60's when Jaynes published it (see below). In contrast to resolutions based on various wild and misguided assumptions on the alleged entropy of the Universe and its value in the past, it is quite prosaic.
The short version of this prose is this: there is no paradox or contradiction between probabilistic reasoning and thermodynamics, because the theorems concluding the same trend for entropy for both the actual and the velocity-reversed specially prepared microstate talk about different kind of entropy than thermodynamics and 2nd law do. People got confused by two different concepts of entropy here.
The derivations actually talk about evolution of some coarse-grained information entropy $I_{CG}$ (or similarly, about minus Boltzmann H-function). This is typically defined for all microstates of the mechanical system, how different soever they are from its microstates compatible with equilibrium thermodynamic state of thermodynamic system modeled.
This is very different concept of entropy from thermodynamic entropy $S$ (Clausius' entropy), which makes sense only for microstates that are compatible with state of thermodynamic equilibrium. For general states of thermodynamic system (for example, its possible non-equilibrium states), the concept of thermodynamic entropy does not generally apply.
Also, any implication of the 2nd law for thermodynamic entropy is restricted to states of equilibrium. Trying to apply it to non-equilibrium states is a suspicious operation that may be useful in some cases, but has no general validity whatsoever.
This means 2nd law actually says nothing about the special microstate imagined or its reverse. Both correspond to highly non-equilibrium thermodynamic state and do not have thermodynamic entropy. The coarse-grained entropy increases, but there is no connection to thermodynamic entropy and thus no contradiction with 2nd law.
2nd law says only that when container with system in equilibrium with thermodynamic entropy $S_1$ is suddenly enlarged so that the system is no longer in equilibrium state, the final equilibrium state of the system will have thermodynamic entropy $S_2 \geq S_1$. There is no problem with thermodynamic entropy increase as time coordinate is decreased below the time of enlargement, because the entropy retains value $S_1$ since the system was in equilibrium state in the original volume.
This is one of the reasons why it makes no sense in thermodynamics to talk about thermodynamic entropy of systems such as living cell, fly, Earth or the Universe. These are not systems in thermodynamic equilibrium and are not eligible for thermodynamic description (in the above restricted sense).
Finally, this means that the above-mentioned derivations actually do not derive 2nd law of thermodynamics at all, but only a theorem about evolution of certain theoretical quantity - information entropy of coarse-grained description $I_{CG}$ - that is only similar in wording to the 2nd law of thermodynamics, but has completely different meaning.
The quantity $I_{CG}$ expresses ignorance about the actual microstate of the system when all we know is a cell in phase space. It is too general as far as allowed microstates go, and too specific as far as cell specification goes, to identify it with thermodynamic entropy in all cases.
Thermodynamic entropy of equilibrium state does correspond to information entropy, but in a very different way; its value is equal to maximum possible value of information entropy given mathematical constraints on the probability distribution implied by the thermodynamic state maintained by physical constraints (volume of the container). This is very different from coarse-graining.
If you got interested, you can read the original and more exhausting explanations in Jaynes' contributions to physics, mainly the papers
http://bayes.wustl.edu/etj/articles/gibbs.vs.boltzmann.pdf
http://bayes.wustl.edu/etj/articles/brandeis.pdf
http://bayes.wustl.edu/etj/articles/mobil.pdf - from page 141
http://bayes.wustl.edu/etj/articles/ccarnot.pdf - sec. 6 & Appendix C