I found the same problem. Reproducable from save Below.
Please also note that in the savegame the enemy emperor is sitting in one of my towns. I have unfortunately no debug.err of the event when he got there, but it happened as follows: I Fought a tactical battle with him to conquer the town. He fled from the battlefield (he run to this grey mist) and was found on that city tile afterwards.
http://dl.dropbox.com/u/9038574/BorderProblems.EleSav
