I have also experienced this bug which has costed me a few important battles. I can add that scouts are able to sneak into the problematic neighboring provinces when the armies fail to travel.
KO:
Any chance we'll see map edit commands where province_A can only travel to province_B? (one_way traveling)
