I’ve seen where although they are removed from sites they have access  to, they have information also contained in the User Information lists on each WSS site  they had access to. Look at this list within a site they had access to… if you see them, this needs to be removed before you can re-add them back to the site.

I will certailny check to see if that is the problem.

they must be removed from the site  collection.