Behavior that I described above pertains to Windows 2008 R2. When I attempt at doing exactly the same with AD set up on top of Windows 2012, it works flawlessly. Unfortunately, environment I have to set up trust with uses Windows 2008 R2. I am wondering what might be the difference between these two versions that prevent trust from working in case of Windows 2008 R2.