I found 16 undiscovered nebulae out of a survey of about 100 in the western galactic core. Of the rest, 80 or so were still uncharted in EDSM and 70 or so of those were basically unexplored. Some of the most prolific nebula hunters from the early years of the game -- CMDR Madraix in particular -- only ever scanned the nebula's core star. The trick is to stay away from heavily trafficked points of interest (Sag A*, core nebulae, etc).
I'm planning a trip to the southwestern core right now; I've currently scoped out a patch of 20 uncharted nebulae within 1000ly of each other. I'm expecting 1-2 will be first discoveries.