hg histgrep will let you search a change log for a pattern, such as a deleted string. If you are looking for more than just the first occurrence, be sure to include the --all flag. For me it looked something like this:
hg histgrep --all -r 9876:tip "pattern" path/to/file
Thanks to Anton for the helpful comments and krtek for his related answer.