EDIT: I have most probably found out the reason thy it works (or doesn't work actually) this way. The problem is that I don't have legitimate access to the user node that is being edited. I only 'hacked' the menu system so it let me through but don't really have the real access. Unfortunately I have no idea how to resolve this problem...
I have reworked the system that handles permission to user edit pages so that it allowed editing certain users even without the 'administer users' permission.
The system itself works well, the only problems are entity reference fields on the user. To be more specific, there are two entity reference fields attached to user bundle -> one that references another user 'supervisor' and another that references certain content type.
The problem with these two fields is that the autocomplete feature (I use autocomplete widgets) in the widgets not only doesn't work but even throws a 'access denied' error (in AJAX response).
It works well when current user has the 'administer users' permission but I can't give every user this permission.
BTW: To make it perfectly clear, not even the field that references a normal content type (node) works so the problem can't be in access to user entities as the answer below suggests.
I have tried to look into the entity reference code but have not found anything that would explain this strange behaviour (there's literally zero calling of user_access that might lead to this kind of behaviour).