So far it seems like setting Max Avoided Walls to 0
resolves the slowdown and stuck issue, however sometimes the Character is entering the Yellow border completely - I am not sure if it is good enough to live with and what setting the MaxAvoidedWalls actually means :-()
Well after more testing I realized that this is even worse 
Now AI are just going on top of un-walkable areas and what not
No, RVO is Disabled!
The generated path is fine - the path following is just bad - It appears like it just wants to cut some corners and then stuck in them