How is this process not quasi-static yet reversible?

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.

In the process you describe the system won't necessarily return to its original state.

Suppose you instantly remove the weight and lift up the piston so the gas expands irreversibly to it's new equilibrium volume. The gas does no work in expanding so its temperature doesn't change - all that happens is that the pressure falls.

Now compress the gas back to it's original volume reversibly by lowering the weight back on very gradually. Now you are doing work on the gas so its temperature increases. When you eventually release the weight you'll find the gas temperature and volume are different to the initial state.

If you do the cycle reversibly you'll find that the work done by the gas as it expands is the same as the work done on the gas as it's compressed, and it will return to its initial state. However this isn't the case if the expansion/compression is not revesible. This is because work is not a function of state.

In the context of equilibrium thermodynamics, when we say that a process is reversible, we usually mean that the process is well-described by a continuous path in thermodynamic state space (namely it is quasi-static) and that the system can be taken along the same path in thermodynamic state space, but in the reverse order. Since in the example you gave, the system is only in equilibrium in the initial and final states, it doesn't make sense to talk about reversibility.

It's true that the system is going from one equilibrium point (point in thermodynamic state space) to another and then back again, but one cannot speak of the system "retracing" its thermodynamic steps so-to-speak because from the perspective of equilibrium thermodynamics, these intermediate steps are not well-defined macroscopic states.