The crawlers run continuously, and the letter might come much later. So, no, they can’t find deleted things, but yes, they’re likely to find infringement when it’s available on the web for any amount of time.
Keep in mind, I’m speaking from experience with stock photography infringement. Comments in this thread give me the impression that the music industry never got quite so draconian, but then again, it also sounds like they have the tools available to become draconian at any moment.
And it also seems to depend on venue. For example, if you put any more than a few seconds of a commercial track in the background of a youtube video, all the monetization for the video will go to the rights holder for that track. That’s pretty draconian! And it doesn’t involve lawyer letters or courts. If you want to appeal, you’re going through youtube bureaucracy, and my impression is that you aren’t likely to prevail.
Adam Neely has an older video about how this really violates the spirit of fair use, but it is what it is.