It occurs to me that it would be more grammatically consistent if I said: "Didn't that bakery use to be a fish shop?"
Spoken aloud they sound pretty similar, and now I wonder whether that's what everyone else says anyway, and I've just never noticed. But then, "use to" in that sense is seldom heard in the present tense these days (e.g. "Do you still use to play golf at the weekend?" sounds pretty archaic, if not downright wrong), so perhaps we've all slid into saying "used to" because that's now the default form of the phrase. Again, it's a small step from:
"That bakery used to be a fish shop."
"Didn't that bakery used to be a fish shop?"
I'm not sure where I'm going with this, to be honest, but I'd be interested in other perspectives on this usage.