I'm not sure if this is a bug, based on the kind of perks they chose at the start of the map. Though I'm not too familiar with Mechanicus perks, I know some races have perks that increas their detection range, meaning they'll detect and fully reveal you at a longer range.
I'm not sure this is the case for you, but if that was the case and they seemed to be out of range of 'your' detection range, but had a perk like that, increasing their range by.... 4500 I think? It would mean they could see you still if they were close enough.. At the same time, seeing a Cairn on the other side of the map isn't that rare, if they use skills or just about any movement increasing effects, it would reveal them I think.