qwertysimo:
Contact the seller?
I think so.
To the point where three of them have been proven kosher, it certainly sounds like you are doing everything right. It is notable that this sort of grief appears to be exclusive to the HC-06 and I won't be buying another. The HC-05 seems a better bet and costs about the same. The only advantage the HC-06 has is that it is a hell of a lot easier to programme than the HC-05! In the matter of naming, I had cause to configure my HC-06 last week. It looked like it had failed to accept the naming command but it was actually OK.
FWIW, I have waxed lyrical about the HC-0x on the JY-MCU over the years, but the latest HC-05 I bought is on a ZS-040 board. This board includes a little press button to facilitate programming, which would appear to make the job easier.
I have just remembered that somebody had a problem with a solder bridge on the backboard. You might check for that.