You guys provided some great info, thanks. I tried searching, but nothing came up.
I ran into this problem yesterday where I had relationships built in mxd, working in service, regular MapServer.
Added a join to the feature in mxd and relates stopped working in REST. Removed join, they work again.
It's really annoying, because now I have to fall back the old method of writing custom service endpoints to perform these queries, then merge them to the spatial data client-side.