This is an expectable behaviour, actually.
Consider how you would handle the buildability in SC. Every tile has a flag if it is buildable at all, and another one that indicates if there is a building on it.
Everytime a building is built, the "buildingThere"-flags for the appropriate tiles are set, and everytime a building is destroyed, the flags are cleared. SC does not allow stacked buildings unless you come up with things that were not planned by Blizzard, so this method would work perfectly, and you don't have to go through the whole unit list and check where all the buildings are placed to find out if some terrain is buildable.
Now if you stack several buildings, the flags are set and set again, which leaves them set, and when you kill one, the flags are cleared and the tiles become buildable.
Note that I have nothing to back this theory up apart from my common sense and my little programming skills, as well as ockham's razor.
But hey, I was right with the way SC handles the STR section (proven by Heimdal - by disassembling I think), so this might be not that a bad explanation