In Minecraft 1.9.1 pre1 a change of mine was added (listed as paper patch in change log), however the implementation was changed from what I passed along, and that change by whoever applied it is what caused the crash. But it seems the patch was reverted instead of fixed.

This patch cleans up some really badly written code and greatly helps performance (avoiding server overloaded issues)

Numerous flaws exist in the current vanilla logic such as the world registering navigation objects into the hashmap for every living entity created even if that entity is not even added to the world.

using a weak hashmap to auto clean up references is simply a hack.
There are already methods in this listener that handles onWorldAdd/onWorldRemove for entities, so its very clean to just use those.

the code is creating a clone of the data every single update call which is very slow and wasting memory.

See patch again:
https://hub.spigotmc.org/stash/projects/SPIGOT/repos/spigot/commits/04266858e3436dafcb20eba5ae3c9f6d63a7c5a9#CraftBukkit-Patches/0150-Optimize-Navigation-Listener.patch

It's important to use a for(; ; ) iteration method to avoid ConcurrentModificationException.

Entity additions will be added to the end of the list, and logically are safe to 'process' in this current iteration, but if you wanted to avoid ticking the navigation object, you could store .size() before iterating.

Removals are queued, and processed outside of this code, so they will never shift the order of the array as it is being ticked.

We've been running this code in Paper and Spigot for weeks now with no issues.