I am running out of ideas so I re-read the whole thread. Something says to me this is related to Windows Group membership and possibly membership in multiple groups.

I know you said their all Domain Admins which is fine, but are all three users in the same set of AD groups? Are they in any local Windows Groups on the problem instance?

If there are any diffs in their memberships trace those through to the SQL Server to ensure User3 does not have a different set of paths to enter the SQL Server, and potentially the database in question.

Also, SQL Server caches a lot of security info as it relates to AD. It might be worth cycling the server with the problem to ensure a clean slate there.