As far as we know, this shouldn't make a difference.
Even though the two domains have trust relationships, you can't scan most machines in the other domain. You did say you scan some of these machines, correct?
We did have another user, you may have read about, who's unscannable (No Privilege) machines had individual software firewalls installed, though this probably isn't the problem in your case since there are so many unscannable.
Are both of your domain controllers running the same OS? (i.e., W2K3 Server)
Have you tried contacting Microsoft support about this issue? At this point I'm not sure how much we can help, but we'd like to know what the solution is so we can help others. Using RegEdit and browsing to something like the path below on the remote machine is often a good test to determine if you have administrator access to the remote machine. NEWT Pro uses the remote registry a great deal to retrieve its information. This will also eliminate NEWT Pro when dealing with Microsoft support.
SOFTWARE\\Microsoft\\Windows\\CurrentVersion\\Uninstall
Please let us know when you come to a solution. And please don't hesitate to ask anything else of us.