The animation for http://507movements.com/mm_349.html is actually a bit misleading, since there are two degrees of freedom: the lateral movements of the lower and upper halves are independent.
No, a lossy algorithm can be idempotent, and in fact any optimal encoder is necessarily idempotent (because there is no need to further degrade an already compressed image). While it's true that most encoders are not actually optimal and often add noise when re-encoding, it's not a theoretical necessity.
The correct mathematical term for "lossy" is "non-surjective": at a given encoding setting, not all inputs can be represented.