When a dependent object is dropped, all the related packages (or plans if on z/OS and using plans) are marked as invalid (not the stored procedure itself). Upon first execution of the invalid package, an automatic rebind is attempted to see if the problem has been corrected, and if it has not, then the package is marked as inoperative and no further automatic rebinds take place (and execution error is returned).
So next time, check for invalid packages, not invalid SP's.