In early game, I had two neighbours. The Unfallen and the Vodyani. 

Both had Exploration ships of course, and I could ask the Unfallen to remove his explo ships from my sphere of influence, but not the Vodyani.

This goes on for a long time. I know there is a timer that you can't ask more often than every X turns. But I never asked the Vodyani to remove their ship. I never got the option to.

Is this per design, and how does it work? Why is it that I get option vs the one but not the other?

The Vodyani start with the Religious political party in power, which has a law that allows them to tresspass and invade freely even in cold war. I believe the law is called Righteous Fury. Considering their mechanics, they would get starved to death very early on if they couldn't do that, so there's a gameplay reason for it as well.