How to stop time-consuming operations?

[kj]

I started a replace-string command that is taking too long (the
file is much bigger than I had realized).  How can I tell Emacs to
abort the operation?  Ctrl-G is not doing it...  (I have a lot of
other buffers open, so I'd really prefer not to kill Emacs altogether.)

(I realize that by the time replies appear to this question, my
Emacs will have probably finished with the operation, but the
problem occurs occasionally, and I'd like to know how best to handle
it.)

TIA!

kj
-- 
NOTE: In my address everything before the first period is backwards;
and the last period, and everything after it, should be discarded.