Why do some melons contain removeable dark tiny bits?
Not growth inside
As you point out it is highly unlikely that these flecks are growth already in the melon when you cut it for a couple of reasons: 1) there's no wound shown in the fruit into which the contamination might have been introduced and 2) it seems you are finding them only on the cut surface, and the odds of cutting the fruit exactly where these very few and small bits happened to be are poor.
Unfortunately, after ruling that possibility out, it's difficult to know where else in your environment these bits might be coming from. The knife is the best possibility, as you guessed, so is your work surface, or your hands, or these could be tiny bits of ash from the air if you have a wood-burning stove, and so on.