This is extremely annoying and quite unfair. I'm hoping Civ III's enhanced diplomatic features will be more fair. Here's the problem:
1. You only have the option to ask someone else to withdraw from your territory if you have a
current peace treaty with them.
2. Peace treaties lapse after ten turns - though not for you. You're still bound to them; the AI isn't. Other Civs, even though the treaty is no longer valid, can demand you leave their territory, but you can't demand the same from them. Also, in these times when the treaty has lapsed, they can steal technologies from you and it's not a cause for war. (Grrrrrrr!

)
3. During the truces, you have no diplomatic options to force their units off your territory except to repeatedly plea for a permanent treaty. They will sometimes hail you and ask you to withdraw from the environs of one of their cities "in the name of goodwill", or they'll say they can see you have your hungry eyes on their city, and their "mighty armies" will soon drive you out. Your only real option is to prepare for more war....
4. The best way to check for lapsed peace treaties is to hail your neighbors every once in a while; if you have the option "Insist you withdraw your troops" then the treaty is still valid. Otherwise they'll either offer to renew the treaty or tell you to go to hell - which means an attack is coming.
Starlifter wrote: Things that I recall affect it are prior contacts that turn, recent contact, spy activity (particularly subversions), treaty type, enemy troops location, and government type.
Yup. If it makes you feel better - it is unfair, and yes they are all out to get you.