Simple question about a gas in a box with a moving wall David Albert is a philosopher of Science at Columbia. His book "Time and Chance" includes this example (p 36). 
A gas is confined on one side of a box with a removable wall. "Draw the wall out, slowly, and perpendicular to its surface, like a piston. Now it happens to be the case, it happens to be a consequence of the Newtonian laws of motion, that a billiard ball which bounces off a receding wall will move more slowly after the collision than before it. (Footnote. Proof: consider the fame of reference in which the wall is at rest.) And so gas particles that bounce off the wall as it it's being drawn out will have their kinetic energy somewhat depleted."
Why is that? We are assuming that an externally applied force is pulling the wall out. It's not the gas that is pushing the wall out. So why is energy lost. Why doesn't that violate conservation of energy.
Another way to look at it is to assume a series of walls very close to each other. Remove them one by one parallel to the surface. There will be no change in the total kinetic energy of the gas. Why is this different?
 A: Do exactly what the passage says to do.  Consider it in the wall's frame of reference.
Say that in the box frame, the wall is moving right at 10 m/s and a particle approaches it at 100 m/s.
In the wall frame, the wall is stationary and a particle approaches it at 90 m/s.  The particle bounces and is now going 90 m/s to the left.
Transforming back to the box frame, the particle is now going 80 m/s to the left.  It's lost speed.  This replicates Kostya's result.
As for where the energy goes, it goes into the wall.  If we imagine the wall being essentially infinitely massive, energy can disappear into it without us being able to tell.  In practice, the gas will do work on the wall, and the external force you mentioned will not be the only force on it.
Finally, as for your thought experiment of removing a series of parallel walls 1-by-1, it is different because the particle is then colliding with a stationary wall.  If the motion of the wall didn't matter in terms of what happens to the particle, baseball players would always bunt.
A: First of all -- we are talking about elastic collisions. I strongly recommend you to read the Wikipedia page.
Let me denote:


*

*$v$ -- speed of the ball before collision

*$m$ -- mass of the ball

*$V$ -- speed of the wall

*$M$ -- mass of the wall


Substituting this into solution, presented on the Wikipedia page (which is, let me stress, derived from the momentum and energy conservation) we get for the speed of the ball after collision,take the limit of the infinite mass of the wall: 
$$v' = \frac{v(m-M)+2MV}{m+M} \quad\xrightarrow{M\to\infty}\quad 2V-v$$
I stress again that the derivation is based on energy conservation.
A: An aspect of this that isn't covered by the other answers is the following: you say "we are assuming that an externally applied force is pulling the wall out. It's not the gas that is pushing the wall out."  But imagine for a moment that the wall is not moving.  The gas is pushing on the wall, so in order for it to remain stationary there must be another force pushing in the other direction.
Now, if we suddenly removed this pushing force and started pulling on the wall, it would move very rapidly, because our pull would be added to the gas's push.  If we want the wall to move slowly then we shouldn't stop the force that's pushing the wall inwards, but just reduce it very slightly, and allow the gas to do the work of pushing the wall outwards.
So if the wall is moving slowly then it really is the gas that's doing the work of moving it, and not a pulling force from somewhere else.  That's why energy can be lost from the gas in this situation without violating the conservation of energy.
Update to address a comment
Russ comments comments that if the wall wasn't moving then no work would be done.  The question, then, is what makes the case of a moving wall different?
The short answer is that work $=$ force $\times$ distance, so if the wall does not move then distance $=0$ and so no work is done, whereas if it does move then the distance is greater than $0$ and so the work is positive.
However, that might not be very enlightening, so let's do a little thought experiment. Let's replace the wall with a piston.  We won't assume this piston has an infinite mass.  Let's say that the piston is rigid (held together by electromagnetic forces, as Russ says).  We'll say that it's not moving right now and is held in place just by being a very tight fit to its mantle. ("Mantle" being the technical term for the cylindrical sleeve that a piston fits into.)  Outside of the piston is a vacuum, just so that there's nothing else pushing on it.
This is the same situation as the box - the piston is held in place by its rigidity and its connection to the sides - it's just that making it into a piston makes the next bit easier to explain.
Now let's imagine that the gas starts to push the piston outwards very slowly.  In this case the pushing force of the gas is almost, but not completely, balanced by the friction of the piston against the mantle walls. We know there must be friction because if there wasn't then the gas would push the piston out very rapidly.
Now, since there is friction there must be heat generated as the piston rubs against the mantle.  Heat is a form of energy, so the question to ask yourself is, where is that energy coming from?  There's nothing touching the piston other than the mantle and the gas, so the only place it really can come from is the kinetic energy of the gas molecules.  The total amount of heat produced is equal to the force the gas exerts on the piston, multiplied by the distance it moves.
If you understand this example it might help you to see why the case where you remove a sequence of stationary walls is different.  In this case there is nothing moving against a frictional force, so there's no heat being generated, and there's nowhere else that the molecules' kinetic energy can go. This is why the energy of a gas does not change when it expands into a vacuum but does change when it pushes against a moving wall.
Finally, it's worth commenting on the difference in approach between this answer and the other ones.  In the other answers, the wall was assumed to move slowly not because there was an opposing force but because the wall was infinitely heavy. If there is no opposing force and the wall is not very heavy then the pressure of the gas will accelerate it until it is not travelling slowly any more.  The "heavy wall" approach allows you to do the kinematic calculations to see how the energy is lost from individual particles, whereas the "opposing force" picture allows you to see what's happening to the energy on a more macroscopic level.  But the same amount of energy will be lost from the gas in either case (the gas can't "know" whether there's a heavy wall or an opposing force), and understanding both cases helps you to get a more complete picture of what's going on.
