To give my view:
Small, incremental changes that leave the code in a better state than it was found
Definitely Yes: "Cosmetic" changes that are not directly related to features (i.e. it's not billable as a change request).
Definitely No: Rewriting large chunks clearly violates the "small, incremental" part. Refactoring is often used as the opposite of a rewrite: instead of doing it again, improve the existing.
Definitely Maybe: Replacing data structures and algorithms is somewhat of a border case. The deciding difference here IMO is the small steps: be ready to to deliver, be ready to work on another case.
Example: Imagine you have a Report Randomizer Module that is slowed down by it's use of a vector. You've profiled that vector insertions are the bottleneck, but unfortunately the module relies on contigous memory in many places so that when using a list, things would break silently.
Rewriting would mean throwing the Module away an building a better and faster one from scratch, just picking some pieces from the old one. Or writing a new core, then fitting it into the existing dialog.
Refactoring would mean to take small steps to remove the pointer arithmetics, so that the switch. Maybe you even create a utility function wrapping the pointer arithmetics, replacing direct pointer manipulation with calls to that function, then switch to an iterator so that the compiler complains about places where pointer arithmetics is still used, then switch to a list
, and then remove the ultility function.
The idea behind is that code gets worse on its own. When fixing bugs and adding features, quality decays in small steps - the meaning of a variable subtly changes, a functions gets an additional parameter that breaks isolation, a loop gets a bit to complex etc. None of these is a real bug, you can't tell a line count that makes the loop to complex, but you hurt readability and maintenance.
Similarly, changing a variable name or extracting a function, aren't tangible improvements of their own. But alltogether, they fight the slow erosion.
Like a wall of pebbles where everyday one falls to the ground. And everyday, one passerby picks it up and puts it back.