Excellent point. One thing that was never asked is "how big is a house?"

Maybe this is the best approach: Compute the desirability influence map in advance, and only update it in case of new buildings or other semi-permanent changes. Then when the AI needs to use it, it should be possible to run some kind of filter over it that excludes tiles currently occupied by people, vehicles, animals and any other transient features (from other influence maps?). The filter would also need to take into account the specific dimensions of the building that needs to be placed, for instance 3*3 or 4*4 tiles.

I wouldn't bother keeping a map for people and what not. They aren't affecting the "desired location" function at all. At that point, it is just a matter of waiting for the zone to clear.

One thing you might consider... once you decide on the footprint for the building, prevent anyone new from moving into that area. Reserve it for the building. Also, if anyone is in that zone, make sure they start to move their ass with a preference on getting out of the building zone. Once the space is clear, the building drops into place. By doing that, you avoid the problem of snapping people out of the building zone. You let it clear naturally instead. But now we are off-topic slightly.