@Schrompf yeah I'm doing soft connections, makes things a little less twitchy than if you go with stiff connections in a case like this. I don't exactly get what you're saying about pulling in limbs? I do get that it would be pretty simple to have a tentacle that just contracts and then extends along a new path. It could just make itself longer along the path, and when a new path is found it could easily use its own body as a path home, and then get started on the next path. Problem is that if the base of the tentacle is moving, such as in this case, it'd be always contracted. So I need something that rather tries to align with a path in real time.
@zorg, I pretty much need to animate it all, because the tip and the base of the tentacle are moving simultaneously. But that's not the problem really - the problem is terrain, or more specifically corners. When the rope is pushed against a corner the segments go separate ways, and end up on different sides of some terrain feature, which causes the rope to get stuck.
Update 382I think I actually solved it to a degree that's far from perfect, but which I'm decently happy with. As marcgfx mentioned, we're hoping for the skinning of the character to make it look better still.

Sometimes the solution was super obvious and sitting there all along. Not so this time. Every part of functionality in this thing was hard won through hours of blood, sweat and tears.

My head is all dizzy from all the actual freaking
thinking I've had to do to get to this somewhat okay-ish result.
Contrary to being obvious my solution is even hard to explain. Hmm.
Okay, so you see that there's a semi-transparent "ghost" tentacle? That's the tile space tentacle. It has pros and cons. Pros - it can never be inside terrain, and the segments are always neighbors, meaning the whole thing is connected from root to tip, in non-solid tiles. Cons - it's square looking and lack physics features such as gravity. But most notably, when the path changes, it tends to curl up and get really small before extending along the path again.
Then there's the float space tentacle, which are the round segments. The idea is basically that the float space tentacle should do it's thing, looking cool and physicsy, but also draw from the strengths of the tile space tentacle (which is, as we remember,
not getting stuck in terrain all the goddamn time).
Each float space segment has a buddy in the tile space tentacle, as indicated by the little purple lines. If the float space buddy can see its tile space buddy, it's pretty much free to float around.
If not, the float space buddy has been keeping track of every position of its tiles space buddy, like, 60 ticks back. So then it starts to go backwards in that list and raytracing to check if it can see those last positions. The first one it can see, it moves towards.
This means that the float space tentacle generally does its thing, except when it can't see its tile space counterpart. In that case it starts to follow like, the ghost of its tile space counterpart, until it catches up. That's why you can see the float space tentacle kind of mimic the movement of the tile space tentacle, but a little bit delayed, as an obstacle is avoided.
Pew.