I have the same problem: relating any tables on fields using GUID's, is not visible to ArcGIS server. Shows up in the REST directory with a relationship ID, but cannot query across the relationship. Kinda wish ESRI would have included this restriction in the help documentation. Adding objectID's to these tables is not an option or a workaround.