In addition to the other options posted here, you can do what 3D games do: they have polygons covering all navigable areas. You then find which polygons connect source to destination, then create lines/curves across them (you never have to path find within an area because other don't contain obstacles). The harder problem is creating these maps, but there are quite a few solutions to that (e.g. voronoi). You could use a quadtree, and your navigation graph would consist of the set of the deepest nodes.

Your current solution seems like it could be a minefield of edge cases.