My problem comes much from where the heightmap comes from. I create an heightmap for each leaf of my quadtree. As I go deeper in the quadtree subdivision, I continuously create heightmap based on miscellanous noise functions. At a given depth (about 14 subdivs) the input coordinates for the noise are too small for a 32 bits float (I'm doing it with the GPU). This precision issue leads to really bad artifacts in the normal map.
Nothing strange about the way normals are computed. There's multiple ways to compute normals. Here I choose a fast and simple shortcut. I Could have used something like sobel filter but it takes more computations and more sampling from the heightmap. Instead, I only do the difference between the top and above Heights for one axis and the difference between left and right Heights for another axis. Given a Y axis = 2.0 for a quadtree depth of 0 I'll have Y=1 for Depth=1; Y=0.5 for Depth=2, Y=0.25 for Depth=3 and so on... (here is why the 1<<pTreeNode->GetDepth() is for.)
For a terrain & if your normal map is computed from a heightmap, you can use world space normal maps. Your normalmap will only be used on the terrain (tangent space allow you to use your normal map on any geometry).