Do magnets lose their magnetism?

The second law of thermodynamics - about the increasing entropy - which is apparently what you're talking about - holds for any system. Permanent magnets are no exception.

A ferromagnet may look "more ordered" than a non-magnetic material because the spins are oriented in the same direction, rather than random directions. But physical systems may only try to maximize their entropy among configurations that conserve energy (much like the momentum, charge, and other conserved quantities). For ferromagnets, the configuration with spins oriented in random directions would have a much higher energy - because one reduces the energy by orienting the spins, elementary magnets, in the same direction.

So the spontaneous disappearance of the uniform electrons' spin would violate the energy conservation.

Among the configurations with the same energy, the magnet still tries to maximize its entropy. In particular, the heat is flowing from warmer pieces of the material to colder ones, and so on. More generally, the entropy never goes down, and that's the only general statement that follows from the second law of thermodynamics.

Ferromagnets are not special among physical objects that could have a higher entropy if you allowed the energy to increase. For example, any object would raise its entropy - the amount of disorder - if its temperature increased. But a higher temperature requires a higher energy, too. One can't violate the first law of thermodynamics (energy conservation) just because it would make it more straightforward to satisfy the second law. Both of them hold in Nature.

Entropy has little to do with magnets loosing their magnetization. The problems is that magnets store large amounts of energy in their magnetic fields. This is usually described as the energy of the demagnetizing field, and it's just another way to refer to the magnetic coupling of individual magnetic dipoles (not the exchange coupling, just the classical dipole-dipole interaction).

A magnetic material can lower this energy by adopting a magnetic configuration that minimizes magnetic charges (i.e. magnetic poles). It does so by moving it's domain walls in a way that lowers the total magnetic moment. A good magnet has many crystallographic defects that pin the walls. However, if the temperature is high enough, and if you wait long enough, the walls will eventually “creep”. This is called “magnetic after-effect” and gives a characteristic variation of the magnetization which is linear in $\log(t)$. This behavior can be explained by the fact that domain walls face a very wide distribution of energy barriers.

Good permanent magnets are supposed to show very little magnetic after-effect. As a special case, single domain magnets are a type of nanomagnets that do not show this after-effect at all, simply because they have no creepy domain walls as they would cost too much exchange energy. An assembly of such particles can however loose its magnetization because of individual particles switching from one magnetic orientation to another. This is called superparamagnetism and is an obstacle to increasing bit density in magnetic storage (i.e. hard drives).

Edit:

There is some evidence that the demagnetization of a magnet is driven by its dipolar energy rather than by entropy. First, there is the van den Berg construction (see for example the book Principles of Nanomagnetism, by Alberto Passos Guimarães). This is a geometrical way of predicting the magnetic configuration that minimizes dipolar energy in a flat magnet. The predicted configurations have actually been seen on real micron-sized samples, when imaged by MFM, Kerr or XMCD. If the walls were driven by the urge to maximize their entropy, then one would see them wandering randomly all around the sample. Instead, on soft samples, they can be seen to adopt the exact configuration that was predicted to minimize the magnetic dipolar energy.

Another evidence is numerical micromagnetics. This is the art of numerically predicting the magnetic configuration of microstructures. The predictions are done by minimizing the total magnetic energy (sum of dipolar, Zeeman, anisotropy and exchange), with little consideration to entropy. The fact that numerical micromagnetics can be quite successful is an evidence that energy is more important than entropy in the behavior of magnets.

On the other hand, if one considers a diluted assembly of magnetic nanoparticles close to their blocking temperature, then the demagnetization of the assembly is actually entropy-driven. Only when the nanoparticles get quite close to one another their interaction energy starts to play a significant role.