Our district originally started with shared iPads and they were a nightmare. We had a different MDM at the time and were constantly removing users from the iPads.

What Apple told us at the time was that during logout the users data is synced to their Apple ID. Once the iPad is fully logged out it is supposed to continue syncing the user data. If the data syncs, the device marks the user as synced or completed. When a new user attempts to login to the iPad it checks if the oldest user has synced all their data. If it has the new user can log in. If not you get the horrible contact your admin message.

I would check with Apple to see if the users data is still syncing once logged out. We switched to 802.1x during our deployment and found Apple had a bug where the WiFi would disconnect during logout and never connect until someone signed into the iPad. This would result in no users data being synced properly. We had to switch all iPads to a PSK network. This was on iOS 10 or so though, so a while go. It was fixed several months after we ran into the problem.

Pulling the logs and sending them to Apple was the only real way we could find out what was happening on the back end. But it sounds like the user data is syncing properly. Can you try connecting a device to a hotspot and logging in and out to see if the data syncs?

Thank you @sdecook!
We've been having some strange behaviours with the WPA2/3 network that might be a clue so I will check up on that.
As this is a quite strange behaviour I going full conspiracy-mode and will check if the magnetlock on our cases might be a cause as well.

This post describes similar problems and the solution mentioned point at a WPS problem (at the bottom of the thread).
https://community.meraki.com/t5/Endpoint-Management-Systems/Shared-iPad-WIFI-and-Log-in-Issues/td-p/23752

We had this issue a lot last year. I think it has something to do with the account still syncing it's data to icloud and getting stuck. The way I got round it was to reset the users password but wasn't great. We've not really had it this year so I guess it may have been fixed in an IOS update?

It really can't be as we have a combination of 12.4.1 and 13.1.3 devices and the problem appears on both. I'm still trying to figure out the reason for this. Today I could confirm that when the user set at prestage (we have 2) was reached the 3rd user was not able to log in.
After manually deleting one of the users via Jamf Pro, the 3rd user was able to log in.

To make things even more confusing, jamf pro does throw a "something when wrong" error when trying to delete one user manually. But after a log out - update inventory it's seems possible to delete the user and the device is usable again.

Gonna continue searching for a more specific way to confirm exactly what breaks the funktion.