I'm pretty sure you're thinking of "Storm Trooper" (1992) by Lawrence Watt-Evans, published in Asimov's, January 1992 and collected in Crosstime Traffic.
The protagonist is Lieutenant Mitsopoulas of the "Discontinuity Control Squad;" New York and the rest of the world are dealing with "reality storms" where things suddenly and randomly change:
"Two years ago we started getting what we call reality storms — and when I say we, I don't just mean me, or New York, I mean the whole friggin' world. For anywhere from about half a second to a couple of hours, the whole world goes nuts in a certain area—things appear and disappear, or change shape, the air can change, the light, colors, everything. Sometimes gravity or even time itself is affected. The size of the storm can range from... well, we don't know the lower limit, but the smallest one anyone's confirmed was about the size of a breadbox. That one lasted about a minute and a half The biggest one reported so far was over the mid-Atlantic, thank God, and was estimated at five miles long and two miles wide. We don't know what’s causing them; nobody does, or at least nobody we know of. [...]
[...] So, anyway, sometimes, after particularly bad storms, there are bits of reality that have been changed permanently, and we get strange things left behind—bits and pieces of other worlds. And yeah, that means that parts of our world are gone, and no, we don't know where they went, and no, none of them have ever come back again. They're just gone, and we've got other stuff there instead, stuff that doesn't always make sense. Like a flying whale—a dead one, with all its gas sacs ruptured, turned up in a Kansas cornfield; that drove the science guys nuts. I don't know about you, but nobody in my world had ever seen a flying whale before, or any other animal that was lighter than air."
They find a new building signed as "New York City Internal Security:"
Simons eased the van over, double-parking it in front of the indicated building. "What is it?" he asked.
"Look at the sign."
Simons looked and read, "New York City Internal Security, Midtown Boo-ro. B-U-R-O? I never saw 'bureau' spelled like that."
"And I never heard of the New York Internal Security," Mitsopoulas said.
"You don't think it's just some rent-a-cop outfit?" Orlando asked from the back.
"I don't know — but that's a damn big building for a rent-a-cop operation I never heard of, and besides, it wasn't here the last time I came past."
The occupants of the building don't understand what's going on:
"Listen," the voice from the building replied, "I don't know who you are really, but if you're the police, who the hell do you think is in here?"
Mitsopoulas blinked, and read the sign again.
Internal Security.
Yeah, that might mean police somewhere, but in New York?
Besides, he knew perfectly well who the cops were here.
But then, there had been a reality storm last night, and it was clear that this building was from some other New York. Were the occupants unaware of what had happened?
Maybe, somehow, they were.
Well, then, someone had to explain it to them. That was simple enough.
Discussions with the "Bureau Commandant" Fitzwater don't go so well, so Mitsopoulas calls for backup:
"We don't use radio," Fitzwater said.
Mitsopoulas groped for a moment for the next idea, and said, "Hey, but we do! Listen, let me talk to my men—let me tell them to call for back-up. Don't you see? If anyone responds, then it's our world out there!"
Fitzwater brought the gun back to his shoulder. "And if no one comes?"
"Then we'll surrender. If you'll guarantee our safety."
And backup arrives:
Another siren shrieked, this one somewhere to the west, probably coming across on Forty-Second Street. Fitzwater stared.
The first of the familiar blue-and-white sedans pulled up, and then a second, and a third, lights flashing, and Mitsopoulas had to fight down an urge to giggle as Fitzwater’s jaw sagged.
[...]
Fitzwater made a strangled noise as car after car discharged New York cops with guns drawn.
