When SP uses index and this index is deleted after the procedure was cached, SP can't execute.
Procedure's optimized BLR resides in the metadata cache. To clear this cache, it's enough to disconnect all users from database. Recompilation is not necessary. It would be nice to allow re-optimization of cached SPs under some circumstances.