Altering Structure order doesn't update cache
After Greg Stewart's help I found that the reason that the Cache wasn't updating when altering the hierarchy of the Structure is:

There were Stuck background tasks.

Here is the official documentation on the matter.