How about this:
When you sign an Open Borders agreement, you may set a turn limit on how long units can stay in each others' borders (Minimum 5). When an AI unit enters your borders, a counter will appear over their heads, tracking the number of turns left. The counter resets upon exiting. If the counter hits zero, you have the right to request tribute. Acceptance resets the counter. Refusal is an automatic DoW.
If Open Borders is canceled, any units that are still inside keep their turn counter, and can stay for as long as the counter allows, but failure to exit in time is an instant DoW.
A DoW does not push enemy units out of your territory.