Not too Perlish but does the client have a firewall(ie zonealarms) or some ad blockers? They will prevent cookies. Does the client also run ad-aware?

Other than that. Make sure the client has all the patches for IE6. Most of my machines have it and do not see the problem you describe.

Finally for W2K/NT/ETC issues. Sunbelt Software runs an NT Admin list that is really good for getting help. Take a look at:

www.w2knews.com