Borek: In other words, both processes are comparable to the freezing and melting of water/ice, i.e. they can go back and forth a virtually unlimited amount of times with no permanent damage/alteration to the original, um...particles?
Do we want to be pedantic here? Reversibility is a statistical concept. An irreversible process is one in which one state (call it B) is statistically favorable over another state (call it A) such that the transformation of A to B is spontaneous, and the transformation from B to A is not. A fundamental principle of chemistry is that all microscopic processes are reversible. Correspondingly, ANY macroscopic process is reversible (practically speaking) provided you are willing and able to supply enough energy to change the system/environment so as to make the reverse process spontaneous. But if the environment doesn't change, then spontaneous changes/processes are not reversible because the environment favors one state over another.
Your ice/water example is a good one. Melting is an irreversible process because if you take an ice cube and lay it on a table in the sun on a hot day, it will melt. But it will not spontaneously reverse and reform an ice cube under those same conditions. The only way to reverse the process is to change the system's conditions - i.e., gather that water and put it in an ice cube tray and stick it in the freezer. So in colloquial language we may consider melting to be reversible, in the sense that we can easily undo it, but this is not the thermodynamic definition of reversible. (You will find much confusion on this point by searching the web.)
A more rigorous thermodynamic way you may look at irreversibility is that in complex transformations, the efficiency is never 100%. You always get some energy loss, so there is no way to go back to the original state without supplying more energy into the system. In the case of ice/water it is easy in practice to reverse the process by simply sticking the melted water back in the freezer. Other cases (e.g., unscrambling an egg) would be virtually impossible. Theoretically, if you were able to microscopically untangle every protein molecule and allow it to refold in its native state, maybe you could reconstitute the albumin to be "unscrambled" - in fact, if your egg white were composed of a single protein molecule (how many proteins does it take before it's considered an egg white?), the process would be quite reversible potentially. But the statistical concept of irreversibility kicks in with macroscopic egg whites, and short of a massive amount of time and energy, this process could never be reversed.
The essential criterion for an irreversible change is whether the entropy of the universe increases as a result of the change. The interpretation of this is that if the entropy of the universe increases, energy is lost from the system to the environment (universe), so it is not possible to restore the system AND the environment to the exact same state it was in before the process started. For example, if the sun melts an ice cube, the sun loses some energy. Refreezing the ice cube doesn't restore that energy to the sun. So although it looks the process is reversed by refreezing the ice cube, the environment has still changed. Therefore the process isn't truly reversible.
So, to sum, any complex, real (macroscopic) process is fundamentally irreversible, because no process is 100% efficient. Truly reversible processes are purely theoretical (isentropic adiabatic process), because it would require that the entropy gain by the universe is zero, or that the system is perfectly insulated from the surroundings.
EDIT: Relating to the original question, whether or not to classify those as reversible or irreversible depends I guess on whether you want them classified according to the strict thermodynamic definition or something more akin to the linguistic meaning of "reversible", i.e., easy to undo with very little effort. That's subjective, of course. As you say, an ice cube melting is reversible if you have a freezer nearby. Much harder if you're in the desert under the blazing afternoon sun
.