(Aside: nothing exists forever - even time crystals - because eventually the universe will be a bunch of infinitely far apart black holes or something. So I'm not sure how that assumption is relevant.)
The examples you gave above are forever; I just started assuming things like eternity and I can go on to assume no external forces/stuff in the way. (So not disagreeing with your initial statement, just adding.)
For example, even ignoring the fact that the sun is going to explode before the universe does, the earth's rotation around the sun is gradually getting slower and slower. If the sun, and the universe, did last forever then the earth would eventually come to a halt.
In the case of these crystals, my impression is that even in that hypothetical never-ending universe, the movement in these crystals would never slow down.
In addition to that, the tidal forces will compress and decompress the mass of both objects, which effectively converts potential energy (the distance between the two objectds) into heat. Even though the moon is on a trajectory to eventually leave earth orbit, every tide that comes in and leaves lowers the rotation speed of the moon. While the moon has no liquids on it's surface, which makes the effect nearly invisible, it does have tides (slight variations in the angle and magnitude of gravity at it's surface) which move objects around and the energy for that does indeed come from orbital decay. Similarly, the earth loses orbital energy to the sun.
"How can something move, and keep moving forever, without expending energy? It seemed an absurd idea — a major break from the accepted laws of physics."
I don't think that something moving forever is a major break from the laws of physics. Consider the following:
(1) An asteroid flies through space forever (doesn't violate laws of physics)
(2) A current persists in a superconductor forever (again, no violation)
(3) Heck, currents can ever persist in non-superconductors (http://en.wikipedia.org/wiki/Persistent_current)
(4) The motion of the Earth around the sun (the two-body problem doesn't violate physics)
(5) Even the motion of an electron around a nucleus is perpetual motion in a sense
(6) The fact that things have temperature means that their molecules are always moving!
(7) Etc.
Anyway, there are many examples of perpetual motion in physics. The key point is that you cannot extract infinite energy from them, just like you can't extract infinite energy from a time crystal. So why does the article act like time crystals are a big deal in this respect?
-A grumpy physicist