Computers join domain at different sites

OK. I think this is a good one.
My host site has 3 domain controllers.
When physically at the host site, while joining a pc to the domain, the pc will often join the domain at a remote site. The computer doesn’t show in AD host site, only at the remote site, until replication takes place.

Each remote site has one DC, and is connected to the host via 56k frame relay.

Regular user authentication seems to work fine, enterprise wide. Each user authenticates to their local DC at their site.

The KCC (Knowledge Consistency Checker) has been turned off enterprise wide.

This did work at one point, but I’m not sure what changed. Any ideas?