Although this isn't obvious, the system doesn't return to its initial state. If you were to very slowly remove the weight from the piston, then the gas would do work on the piston as you removed it, which means that its internal energy would be reduced. If you remove the weight very quickly then the gas still does work on it, but it will do less work than it would in the reversible case, which means that its internal energy will change by a different amount.
There are several possible reasons why the work can be less. One is discussed in John Rennie's answer --- if you lift the piston so rapidly that the gas molecules can't catch up with it then they will do no work at all. However, a much more realistic scenario is that once you remove the weight, the piston starts to oscillate up and down. After a while the oscillations reduce in amplitude due to frictional dissipation in the gas, and the piston comes to a stop.
In this scenario, under normal everyday conditions, the gas stays at a pretty homogeneous pressure the whole time, meaning that the vacuum effect discussed above isn't very important. Instead what happens is that the gas does work to push the piston up, in pretty much exactly the same way as it would in the non-reversible case. Once the piston gets to the equilibrium position, the gas is in pretty much the same state it reaches in the quasi-static case. The difference is that the piston still has some kinetic energy, which is why it keeps moving upwards and begins to oscillate. Once the oscillations have died down, the kinetic energy that was in the piston is now in the gas, in the form of thermal motion of its molecules. Therefore, once the piston has stopped moving, the gas is at a higher temperature than it would have reached in the quasi-static case.
Once you put the weight back onto the piston, the same thing happens: the gas gets compressed, pretty much reversibly, but the piston still has kinetic energy, so it oscillates. Once the oscillations die down, the gas will have a little bit more thermal energy than it would have done otherwise.
This means that, after removing and replacing the weight, you haven't restored the gas to exactly its initial thermodynamic state. Instead you've heated it up very slightly.
To put some numbers to this, let's assume that the weight you remove has a much smaller mass than that of the piston itself, so that we can assume the pressure is constant. (There's no real need to do this - it would be easy enough to consider changes in pressure due to the ideal gas law - I'd just like to keep it simple.) We'll also assume the volume (and therefore total heat capacity) of the gas is big enough that its temperature stays approximately constant.
So: let's you remove a mass $m$ and the piston starts to oscillate, but eventually comes to rest a distance $\Delta h$ higher than it was before you removed the weight. If you had removed the weight slowly then the gas would have done work equal to $mg\Delta h$ to move the piston, and therefore it would have lost this amount of energy. In reality the gas did do (most of) this work, but it was turned into kinetic energy and then went back into the gas, so its internal energy actually changed by zero. However, replacing the weight does cause a net amount of work to be done in compressing the gas. The oscillations mean that slightly more work than $mg\Delta h$ will be done in the non-quasi-static case. We'd need to do the full ideal gas equation calculation to work out how much, but we know it must be at least $mg\Delta h$. So the total internal energy change after removing and replacing the weight is $\Delta U \ge 0 + mg\Delta h = mg\Delta h$. So the gas has more energy at the end of the process than it did at the start, as claimed.
You specified that the piston is adiabatic, but we can do a similar analysis in the case of an isothermal situation. In this case the gas does end up in exactly its initial state, but it exports a little bit of energy into the heat bath. If you consider the system and the heat bath together, the final state is slightly different from the initial one, because the heat bath ends up with more energy than it started with.
This is generally what will happen in an irreversible process: the final state of the system and its surroundings will be different than in the irreversible case. Very often, but not always, this difference will be in the form of a slightly higher internal energy. It might not always be obvious, but it will always be there if you analyse the process carefully enough.
Nevertheless, there are plenty of processes that are (practically) thermodynamically reversible while not being quasi-static. A simple example is an ideal frictionless pendulum, which repeatedly converts gravitational potential energy into kinetic energy and back again, always returning to exactly its initial state. Of course, no real pendulum is completely frictionless (just as no real process is completely quasi-static), but you can get pretty close with good engineering.
Best Answer
The entropy of the surroundings does change infinitesimally. But the surroundings are large and such a change does not change the total entropy of the surroundings in any sensible way.
Indeed, one already uses that fact in putting the system through a series of reversible steps. As you point out, if the temperature of system and surrounding were in fact identical, no heat would flow. But they are infinitesimally different and so an infinitesimal amount of heat does flow.
The same applies to the surroundings. It too is undergoing a reversible change.