Trust relationship madness, help before I go completely madd!

I'm experiencing multiple issues (not all directly related I'm sure) with connecting Windows 2000 and Windows XP systems to a Windows NT 4 domain.  It seems to have become much worse lately and for unknown reasons.

My network is made up of (listing only what I feel are the relevant components):
Primary file/print servers: Netware 5.0
PDC on NT 4 server (SP6a): SQL database
BDC on NT 4 server (SP6a): Exchange 5.5
Several Windows 2000 (fully patched) operating like "servers" sharing a bank of DVD drives and a large volume of disk space.  These computers act like libraries with static data on them.

Workstations: 90% Windows 2000 with Netware client 4.89 with some on 4.90 SP2 (or 3 or 4 lost track!)

Everything was relatively peaceful until (this may not all be to blame or relevant):
- I began introducing XP Pro systems into the equation (laptops and a few "test" desktops);
- I replaced all 14 DVD-ROM drives on the library "servers" with newer models that accepting the newer dual layer DVD-Rs (this means all the shares had to be re-newed);

There are several problems now (I thank you for your perseverance in reading this) and because they are slightly different issues, I will reward points individually for each question answered with a solution where I require one. Questions are numbered in brackets [].

PROBLEM 1: Logging in from an XP (SP1) computer will often produce the error, "The trust relationship between this workstation and the primary domain failed"
Now, this issue manifests itself in two ways (believe it or not): 1) It simply will always display this message and not allow a log in to the Windows domain or 2) If the client WAITS a few minutes (seriously, anywhere from 2m to ~10m), the client can log in without an error [1].   On the other hand, sometimes even the wait doesn't seem to help!

 I'm sure many have seen this error and in fact, there are 1000's of references and proposed fixes on the web.  I've tried many of them and only one solution seemed to consistently work.  Unfortunately, I #$%@ lost the solution! I recall it required a security flag to be changed in the local security policy [2].

PROBLEM 2: This involves a relatively new problem with clients accessing the library "servers". Even if a client doesn't have a problem logging into the NT domain (most often using a Win2K desktop), accessing the library "servers" resources is prevented by the same or similar "trust relationship" error.  As an administrator, I sometimes see this error as well but more often this error doesn't occur. [3]
Also puzzling is the inconsistency of the login prompt appearing when trying to access the library resources [4].  Even though each library server is supposed to allow access by authenticated clients (heck, at one point even everyone was set), these servers still request authentication (user name and password box pops up) BUT it will only accept an administrator's credentials! [5]   Like I stated, it sometimes errors with the "trust relationship error", sometimes allowing a non-admin. access without hesitation, and sometimes asks for a user name and password (but only allowing access to those few with admin. privs.).

I should point out (so that this doesn't seem like a complete mess) that there are absolutely no issues in clients accessing their email through outlook to the Exchange 5.5 or SQL servers (both running on NT4) and they are remarkably responsive especially considering that they are only PII 300MHz computers.

To recap:

[1] What are the possible reasons for the "trust relationship" error to just disappear if the client waits a certain about of time?  This can be repeated in fairly rapid succession just by rebooting so I don't believe this is a "memory effect" issue.  This problem is repeatable every time (before [2] was solved - still, I'm curious!);

[2] Tell me how to fix this "trust relationship" problem.  UPDATE: I found what I was looking for in question [2] - the solution:  local security policy\Local Policies\Security Options\"Domain Member: Digitally encrypt or sign secure channel data (always)" select Disable and re-join domain if necessary.  There! I'm feeling a little better now!  Works like a charm!  Hey, I'll offer points if you answer this:
[2b] I attempted to make a .reg registry fix for this solution but the mystery is that value (4 and 0) in registry doesn't seem to change whether it's set to enable or disable!  Am I in the wrong place?

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\SeCEdit\Reg Values\MACHINE/System/CurrentControlSet/Services/Netlogon/Parameters/RequireSignOrSeal]
"ValueType"=dword:00000004
"DisplayType"=dword:00000000
"DisplayName"="Domain member: Digitally encrypt or sign secure channel data (always)"

[3] Why am I seeing this "trust relationship error" when accessing the library "servers" after there were no initial login issues?

[4] Why is this problem so inconsistent (which has made it difficult to diagnose)?

[5] How do I fix this problem so that the entire company can log into these library servers without requiring any additional login as is  already the case with the PDC and BDC?

Thank you,
Mr.C