What you need to do is add the special local Interactive group to the local Administrators group.

Only locally logged in users have thier security tokens added to the special Interactive group.

You will then have a member in the group that looks something like:

NT AUTHORITY\INTERACTIVE (S-1-5-4)

For the NT 4.0 machines, remotely manage them from a W2K machine to add the special interactive group.