Erik-
you can't serve map joins, at least I never could. You can however, serve a spatial view or if that's not possible set up a gp to create a layer out of your join, store it in a file gdb that is in a sever-registered location and inlcude that as part of your map service.
David