Behold the mighty power of the NavMesh... :)
Sometimes they seem to block each other off from finding a new destination, so maybe I would have to give them some watchdog for that.
I had a Coroutine in for randomly re-deciding on the path, that didn't work so I threw it out (it was also a remnant of my initial attempt for a movement system). Maybe if I gave it another attempt to make it work and set its interval much lower than it was, it might just do what would be needed here...