I have the same problem and i already created a interdomain trust , a two-way trust in "Active Directory Domains and Trusts" the trust relationship between my two different domains is Validated on both AD's but the firewall client keep unauthenticated.
I do a fresh install with windows 2003 sp1(with last hotfixes), than , install isa 2004 standard edition , pass sp1 , and put the machine on the users domain , at this point all work perfect , i do the same clean install , but now i dcpromo and the firewall client is broken again..
I try a lot of things , i check a lot of configurations , but i have no success with firewall client authentication , please any Guru can iluminate and help me.! please..!?
One Difference , both of my AD's is windows 2003 , the solution i think is more secure is about have 2 AD's , one for ISA , one for internal corp domain , make a one way trust between isa's domain and internal corporate domain ,and grant access for authenticated users on internal corporate domain throught isa 2004. In this inicial step i put isa 2004 and w2k3AD on the same machine , in future i try to break on 2 machines.
Thanks for help and sorry my Bad English ... 0zburn.