Somehow, I was unaware of C-M-% for replacements, though I use M-% all the time for a (naive) string search then replace all instances by pressing the ! key.
This is a very neat trick, and little things like this are why I keep using Emacs. Part of me wishes there were some "universal" version of the M-: keybind for evaluating elisp expressions in any interactive command.