i have something similiar to it when i have military access to neighbour of a province that ins't connected to our capital,
situation:
- i was playing Brazil and have a huge chunk of land(africa + middle east) with a port in africa, then a railway linking everything to istambul in turkey.
- i forget that i have military access on bulgaria.
- i was constantly get "supply not getting to port", despite i have railways connecting istambul to my major port.
- i blocked the sea zone, forced it use the land route. it worked, but i find it not a proper solution.
- then when i figured out that i have military acess to bulgaria, i canceled it to see what happen, then everything went to normal.
- so its seems for some reason, if u have military access to neighbour of your state not connected to your capital, it can mess supply route calculus.