A sharing rule has been deleted. But users can still see the records shared by that sharing
rule. The system does not seem to be acknowledging that the sharing rule has been deleted.
What should be done to overcome this issue?

Answer: In order to make sure that sharing rules are calculated and acknowledged as they should be, recalculate the rules.

Explanation:
Recalculate sharing rules by: a. Navigate to Setup| Security
Controls| Sharing Settings b. Under the object where the
sharing rule was created or deleted, click on ‘Recalculate’. This
will reset the record permissions for the object.