I have done quite a bit of experimentation with this and I have found one place in the code that just might be the source of the problem. It being a probabilistic problem dependent on random factors I'm not 100% sure that it's fixed now but I had a couple of hundred shops generated for me and all of them looked splendidly connected. So at least things didn't get any worse... let's see if this pops up ever again.