Very frustrating yes, this is a long game. There are a lot of NPR, I have found 10 until now so the galaxy is well populated.
Thanks a lot for your feedback mike2R! Following your tip, my first thing was to check a system I knew had many wrecks and populated with what I think is a spoiler. Adding tracking stations I found there was a big NPR fleet immobile there. So, I SMed in a doomship, killed the spoiler ships, the NPR fleet started moving afterwards. Quickly after there was a battle in the system (I had put my tracking station at the same colony than the spoiler so its ground forces destroyed them, I'm not sure what exactly happened) and now everything is back to normal.
At that point I was really thinking of giving up with the game.