I just figured out my problem. I am doing the query on a FeatureServer layer so that I could edit the related records. Though I haven't been able to find any documentation on this, I don't think that is supported for many-to-many relationships. When I performed the same query on the layer using MapServer, it worked just fine.
So, ESRI, is this correct... Web editing of related tables that participate in a many-many relationship is NOT supported?