This is not correct. Deactivated users are not immediately removed from the users directory, but they should be removed when the job that refreshes the user directory is run. That job runs once per day.
The code that adds and removes users from the directory checks that the user is active. This means that inactive users who were once active on your site should be removed from the users directory within one day of their being deactivated. Users who have never been active on your site, for example, a user who signs up and then doesn’t respond to the activation email, should never show up in the users directory.
For sites that have enabled the must approve users site setting, unapproved users will not be added to the users directory.
Let me know if this is not what you are finding on your site.