Actually i'm developed a very similar project for my bot, i called it profile generator.
It uses wowhead as database (parses objects and mobs), reads maps for background directly from mpq (you can zoom in/zoom out to see entire continent).
It generates profile (for fly/ground gathering) according parsed nodes, you can also move, delete waypoints and nodes, blacklist/unblacklist nodes.
I'm using RD navmesh implementation in my bot, for every waypoint in profile it gets max polyheight value for height, then adds to height a constant value, after that it smooths out segment in 3D (actually it normalizes Z) and that's all.
I'm not using traceline in my bot navigator, it simply flys for waypoints, stucks happens in some zones, for example borean tundra, in some places it has a deep pits, but you can load profile and simply edit this place (just move waypoints from these pits).
So if you getting height without a navmesh, i don't know any reason to waste time for implementation it in your project.
Can you generate profile for Uldum and upload it somewhere, i can compare it with profile from my generator and see where's differences.