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.