Construction costs are deducted when you first put the building down, then an additional amount is deducted upon completion (i.e., for a palace, 200 to start construction, 500 upon completion).  In addition, sometimes further amounts are deducted during construction, usually in the first few turns.  None of these pending costs appear in the cost summaries for the cities or kingdom.

A related bug on construction - when you run out of tiles, demolishing a building does not free up any new construction space.