I am surprised LloyceV would say it should not happen because I know he knows about vanity addresses/search. If one is searching for 1Bxyz, in a given range, you will find many, and obviously if you are searching in a given range, many keys will be "close".
I have never seen this behaviour in
vanitygen. I think it should always get a new random starting point after finding a match, otherwise the private keys you create are linked together, and compromising one means someone could brute force your other addresses.