I don't have a problem with that kind of coincidence, because I think they happen every single day everywhere. If you are willing to realise and admit them.
Sherlock was just waiting for some loose ends to wrap up. He was keeping his eyes open everywhere in case he would spot the one thing that could lead him further. I suppose he saw the phone book, thought: "well, an empty flat directly next to that shop, that's too good to be true" and "that would be quite a coincidence, not very likely"... but then, he is curious and thourough and maybe he thought: "it's unlikely, but who knows... better let's give it a go" and it worked out. Also suspicions can be very strong. I would think that somebody like Sherlock, despite being rational in his methods, would still always act on a suspicion instead of ignoring it.
I've experienced coincidences like this. They do happen. Coincidences make good stories. If I want to tell a good story to friends, I'll tell them about the surprising and unexpected things that happened to me. A TV show tells a story. It works for me, doesn't feel far-fetched