The random element here sounds really strange ... Could you take a backup of one of the players' dat file and attach it here? Then wait for the skin change and ddop it here again?
That could help us see what's happening behind tge scenes.

Also, do all players experience the random changes or only a few?

Are all using vanilla launchers?

We're using TLaunchers

That's probably the issue, as tlauncher changes the skin loading.
Some have said to me that there's a toggle for skins in there, but I'm not sure as I won't use it.

As tlauncher is not supported (due to piracy), I'm closing this.