Hi Jay,
You mentioned that you are using a join and that the database is a SQL server.
Q: is the join coming form the same database?
I am thinking that the layers or the users have a rights problem on the data.
what some times happen is that a person connects to the data-source in database_1 and the other using database_2 but not both are registered or the ArcGIS server.
Also make sure that the instance and user specified in the Database connection is the one registered with the server some time the database is registered but with the wrong user or only using the server name and not the full name "FQDN"
Right click your server connection in ArcMap go to server properties, select Data Store then the MSSQL server that is used then click properties -the finger under the x- then click edit the details must be the same as the Database connection
is ODBC 13 for SQLServer installed on both the server and the station that publishes?
I don't think this is your problem but a common problem.
Deleting the connection Strings and recreating them might also solve the problem as they corrupt every now and then
I hope something helps
Regards
Henry