I think the problem was that I manually deleted my cookies a few times while testing. Among them was a cookie called “wordpress_logged_in_{token}” where {token} is an unique identifier. My best guess is that lack of this cookie caused issues with nonce creation or/and verification. It was hard to notice because I was still able to browse the admin panel (it looks like there WP is using a different cookie called “wordpress_{token}”) and on the front end this website doesn’t show user status anywhere (accounts are not used there, however login functionality is there, just hidden from the view).
The solution was very simple – I just re-logged as admin and my AJAX started working for the admin as well. So if someone runs into a similar issue, make sure that when you clear cookies, you either delete only ones that you need to remove/regenerate or, if you delete all of them like I did, make sure to re-log as admin.
PS: I’m sorry I didn’t provide all the details from the start, but I did try to provide as much information as necessary. I knew I was missing something and now I feel stupid for even asking this question. However, I’m not going to delete it so that maybe someone who runs into the same issue could save some time.