My experience mirrors your own.
Have you tried manually calculating whether the layer is within the scale range?
e.g.
MapLayer associatedMapLayer = map.MapLayers[associatedFeatureLayer.Name];
//InScaleRange method doesn't seem to work, MapLayer.MinScale and MapLayer.MaxScale
//values seem to be wrong way around, so calculate our own
bool inScaleRange = (map.Scale <= associatedMapLayer.MinScale) && (map.Scale >= associatedMapLayer.MaxScale);
//if (associatedMapLayer.Visible /*&& associatedMapLayer.InScaleRange(map.Scale)*/)
if (associatedMapLayer.Visible && inScaleRange)
{...}