Try logging in to the different machines using the same OS user name as it is referred by in the MXD. Suppose the MXD has been storing data layers which comes from DOMAIN\TEST_USER as user name in Arc Catalog's connection properties. If you login to different client on the same DOMAIN as TEST_USER as user name you can verify that all the layers in the MXD will be displaying properly without any Red exclamation marks. This behavior is because you are using the same OS user on all the machines as it was set in the original MXD. If users connect with their own OS user names and password then the MXD finds the data source information for all the layers to be different. The solution to this would be to click on any one red mark and set the new datasource.All the feature data source will be set out automatically. Remember to save the MXD after this. The next time you open the MXD all the layers will be working fine now.