Player Skins often disappear in Multiplayer and become standard skins

My friends and me play on a server of 4 to 6 people in online mode on Hamachi.
Sometimes the playerskins change from the own costum skin to the standard Steve skin.
The issue seems to be completly random, so some skins stay costum and some become Steves.

*What actually happened was...:

• Skins change from and to Steve randomly

*What we tried to fix:

• Log off and in again
• restart Minecraft
• restart the server

*How to repodruce:

• Play together on a Minecraftserver with 1.4.1 or higher (1.4.2)