Don't believe everything you think.
Yes, I already drop bread-crumbs. All player characters drop them, but only the designated leader's are considered, for the most part. Bread crumbs are generated at 5Hz, which is sufficient for most situations before the "stuck" code has to do anything. I have a separate pathing routine that determines the quickest path to the nearest leader breadcrumb. It is this later pathing routine that sometimes gets me in trouble, e.g. when a knockback occurs in BRD or UBRS, and the player character decides to walk off the ledge because the pathing messed up when trying to return to the leader.
I really liked your implementation of using a pre-generated nav-mesh, also, in the screenshots you provided, it looks really pretty.
(The title is in reference to how the original Pacman, and later implementations on other systems, implemented the pathing for ghosts when they began chasing the player, using a basic "breadcrumb trail." IIRC, the original Pacman used a 2D array of two-bit values that indicated the direction of the player as they left the current cell. Later implementations, such as on the Amiga, used a fixed length circular buffer.)