I cannot find any documentation to support this, but in practice it seems that running incremental user profile AD syncs does NOT mark missing users for deletion.
Running a full sync however will mark profiles for deletion, and those profiles will then get removed the next time MySite Cleanup job runs.
So according to my testing if we only ever run incremental syncs then old users will never get removed. Seem a bit odd. Is this the behaviour that others are seeing?