I have seen this happening in my field twice. Both researchers became famous because they did some research that was completed by others before its time being completely unaware of that research existence. Neither the editors, or the referees helped with this.
In one case, the researcher who was in this situation learned from colleagues that similar work was done in the 70's by a prominent Russian scientist, so he acknowledged it, and everyone is citing the Russian guy ever since. The good outcome is that the Russian guy made his re-entry in the field and made more contributions.
In the other case, the original paper was written by a Japanese scientist, who was a postdoc at the time, and everyone forgot about it. Three years later, another researcher wrote a very similar paper, became famous for it, but never cited the Japanese guy. In fact, very few people in the field cite him.
Since many fields are becoming increasingly multidisciplinary, I don't believe a single guy can do proper literature search. You can use google and web of science and whatever tools, but unless you are specialist in a field, you are very likely to miss something. Even if your random walk from citation to citation takes a significant percentage of your time, it may not be ergodic. For better ergodicity is good to have conversations with older scientists who might have stumbled upon your reference in the past. In any case, if you succeed to do your literature search properly, you will notice that there are a few others who didn't. The most unpleasant are the ones that should have cited you, and don't even answer the email you send them.
To answer the question, I don't believe it's plagiarism. In fact, before the advent of specialized science journals, it was quite a common situation in science. -- Remember all those two-name theorems from mathematics. Many of them were developed years apart by different scientists.