I’m going to WAG here, so someone is going to have to come in and answer in more detail…
So, to start with, you’ve correctly identified to separate issues (1) whether you have permission to leave a country and (2) whether you have permission to enter another country.
Every country that I’m aware of in the modern era claims the power to stop people from leaving the country (usually it’s for accused criminals to prevent them fleeing trial, but it can be for other things as well). The Nazis and the Soviets both did this in varying degrees for various groups of people and for various reasons.
And, of course, every country claims the power to stop people from entering the country. An entry visa is simply a document from the country that says you have been granted permission to enter.
Now, let’s get to Sugihara…
From the wiki article on him, it appears that he was operating from Soviet-occupied Lithuania, prior to the Nazi invasion of the Soviet Union. So, he was writing entry visas to Japan for people in then-Soviet-occupied Lithuania. The Soviets certainly could have claimed the power to stop him, so why didn’t they in this particular case?
My guess, and it’s a guess, is that the Soviets didn’t want to cause too many waves with the Japanese at this point. They had just gotten done with the 1939 Soviet-Japanese war, and (I think) there were low-level talks going on with the Japanese with what would eventually become the Soviet-Japanese Non-Agression Pact (signed 1941). This was probably a period where they didn’t see any point in causing an international ruckus with the Japanese.
Also (and again a guess), letting people leave newly-occupied Lithuania just meant less people for the Soviets to have to deal with for the occupation. Plus, from the wiki article, it looks like the Soviets were able to charge a lot of money for transport, so they probably viewed it as a money-making endeavor.
I think this it’s going to be the case for each of the people you mention that we’d have to look at the individual details. Sometimes people were able to leave Nazi territory through bribery or smuggling, and sometimes people were able to leave because the Nazis hadn’t gotten around to setting up the necessary checkpoints yet. It’s going to be heavily time and place dependent.