Yes! This should not happen. Unless you altered the source to search from a specific starting point.

I've never used VanitySearch (because I hardly trust any new software), and I don't know how it works internally, but I would expect it to generate a new random private key after finding a match. I think it's okay to add "+1" from a random number to search the next one (which I expect to be much faster than generating new private keys all the time), but two similar private keys shouldn't happen.