Hi Giorgio,
In Site Settings there is a checkbox for "Really Delete Users?". If that is not checked then the user is only flagged as deleted in the database but not really deleted. If you check that box then it will really delete the user and any newsletter subscriptions. Keep in mind that a person can subscribe to newsletters without registering on the site so there is only a loose connection between newsletter subscribers and site users. You can also delete the subscription without deleting a user. The count is correct because the subscription was not deleted, so it isn't a bug.
Hope that helps,
Joe