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.
It needs to be made clear what "reversible" means in this context. A process is thermodynamically reversible if it can be perfectly reversed (so it retraces all past macroscopic states in opposite order) by an arbitrarily small change in system conditions, such as temperature or pressure somewhere.
For example, air inside a cylinder with a movable piston pushed back by Earth's atmosphere and pushed/pulled by some other external force (a hand, a motor) can undergo a compression process or expansion process depending on which direction the piston is moving. When this process can be perfectly reversed by a very small change in the external force acting on the piston, the process is thermodynamically reversible.
This can only happen when the piston is moving very slowly, otherwise gas inside would produce eddy currents, pressure and heat waves, so-called non-equilibrium states that can't be made to be exactly retraced by some macroscopic action. So thermodynamic reversibility requires that processes are very slow.
Process being very slow is not always enough to be thermodynamically reversible, mostly because of friction. Consider what happens when the piston experiences large static friction on its outer edge. No matter how slow the piston moves, the friction will still be there, dissipating work into heat, thus heating up the cylinder and piston and the air layers close to them. Then it would be impossible to reverse the compression/expansion process exactly just by small change of force, because in both directions of motion, work is lost to heating up the cylinder. So to approach thermodynamically reversible motion, roughly speaking it has to be both slow enough to prevent non-equilibrium states, and friction has to be minimized.
Best Answer
The problem with irreversible transformations, even if quasi-static, is that one needs to add some non-equilibrium quantities to the set of variables describing the system's state. In this sense, we cannot represent an irreversible process by using only state variables.
Indeed, if there is some internal entropy production, this gives an additional contribution to the change of entropy related to the heat fluxes. From a more mathematical point of view, entropy production would make a function of the thermodynamic state a multi-valued object. In this sense, it cannot be represented as a unique curve on the state space.