Não estou sugerindo que você faça dessa maneira, mas resolvi esse problema usando o Active Directory para gerenciar minha autenticação centralizada e implementei o Likewise Open para autenticar minhas máquinas Linux. O LWO fornece um UID e um GID consistentes em todas as máquinas porque são baseados em um hash. Isso faz coisas como o NFS e o rsync serem muito fáceis de lidar. Também resolve bem grupos aninhados.
Você está usando algum tipo de autenticação centralizada como NIS ou LDAP?