Why? Apparently, the Tribute Kulan was paying me allowed him to trespass. The "Get off my lawn" option in the diplomacy screen was grayed out. Once the period of tribute ended, I was able to demand his departure.
During the twelve turns he was there, he summoned an ice elemental, so at least he wasn't just lazing around!
But it seemed he was flummoxed by my city between a mountain range and the sea.
