When I delete "Watch Me Do" from Automator, does it get deleted forever?
If you are referring to the changes you made being deleted (i.e., the stuff it watched you do), I expect it is permanently deleted.

The action itself (in the source list) oughtn't ever be deleted.