With git log -p -S 'string' I can scroll and search through all changes, but I don't know how to limit the output to a certain commit ...
This part is easy enough: git log's main function is to walk (backwards, as Git always does) through commits, one by one, starting from some particular commit. The default is to start from the HEAD commit, if you don't specify which commit to start from, and to keep going forever. But if you do specify one particular commit, it will start from there—and, using -n, you can tell it how many commits to walk through, so if you set this to 1, it will "walk backwards" zero more times after walking through the one commit you specify:
git log -n 1 -p -S 'string' <hash-id>
for instance.
You can also use --no-walk to the same effect. This is more useful if you want to examine two or three specific commits:
git log --no-walk -p -S 'string' <hash1> <hash2> <hash3>
for instance.
and I cannot filter for deletions in advance (I could start my regex with ^- but that's messy).
Here, git log is not really much help. You can, however, redirect the output of git log to a file, then open the file with any suitable command that lets you find the deletions easily (grep, your editor, whatever).
Note that ^-.*<string> does not mean look for changes that are deletions but rather look for changed text that starts with -. Unless you're looking at patch files themselves, so that the text in the file starts with -, this won't help. The - generated by git log as part of the patch shown is not included in the regex search, even with --pickaxe-regex.
You might instead consider using git blame with --reverse.