The fluff description of the Navigator power The Lidless Stare seems to indicate that it might be a mind-affecting power, but the rules text doesn't have anything to say on it beyond the fact that it's an opposed willpower roll. Would it still work on things like Servitors or other things with the Machine trait?

I would say yes, but on a case by case basis. Most multi-tasked Servitors and cyber/psyber animals still have enough of their mind to likely be effected. Cherubims and Servoskulls probably not. In the case of most Imperial creations with the machine trait, they still have significant portions of brain matter which may be vulnerable.

As a basic indicator, consider most servitors and their like with a Machine Trait of 1-3 as likely to be susceptible and those with 4 and 5 least likely.

-=Brother Praetus=-