Earlier quoted context omitted.
That sounds like an issue (and a big issue at that) with the API your engine is providing to you, rather than an issue inherent in A*! Building/rebuilding a navmesh is the expensive bit, cell look-ups ought to be essentially 'free', performance-wise. In an engine like Unity a physics raycast is a super expensive call to make, so if that's also the case for your situation then that's a real shame, I hope you can work…
I could go into more detail, but it would be off topic and lengthy. If you really are interested, see [1] [1] https://github.com/John-Nagle/lslutils/blob/master/npc/READM...
I was genuinely interested, and, wow. It's been 15 years since I've tried Second Life but I'm not terribly surprised the scripting/modding looks like this, and all your comments about the exposed API make sense now.