In most cases users are created in local databases on SP side the moment user logs in through the IDP for the first time. And as user always has to authenticate through IDP in order to access SP, it is safe (from security point of view) to keep users which were de-activated at IDP as active on SP-side (as they won't be able to login to SP anyway).
One approach to keep the SP database clean is to automatically remove or de-activate users which haven't logged-in for certain amount of time. The user will then be re-created or re-activated the moment he gets re-enabled on IDP and tries to access the SP again.
Another approach is to create a custom synchronization process between IDP and SP (e.g. make a CSV dump from IDP and periodically import to SP).
The Name Identifier Management Profile with "Terminate" request could be used for this purpose, with synchronous binding it's just a web service SOAP call from IDP to SP. But most SP implementations don't support this profile, and most (if not all) IDPs would require some amount of customization to make the call at the right time.