The key is to clean up the code you are most likely to work in again.
Working in well-factored code is more fun and more likely to produce the desired result. Those are both important.
However, refactoring takes time, and all edits carry risk of new bugs. Refactoring code that you don't otherwise need to work in is a bad idea.
How to know what code you need to work in? Changes tend to happen together, in high-churn areas, while other areas are left idle for a long time. There are many reasons for this phenomon; one is that the changes you make right now are probably wrong, but you can't know that until they're done.
So, I use the following sequence when working on a feature or bug fix:
Imagine what the code would look like if it was ideal for the change I want to make, so that the change would be a simple one-line edit that was obviously correct?
Imagine a path of refactorings to get things to that point.
Make one refactoring at a time, testing as I go, and checking in each refactoring separately, with a special change description that starts with "REFACTORING:". This helps make it obvious that if you're looking for a deliberate behavior change, you don't have to look at this one. Also, since most refactorings are well-defined with well-known names, it is easy to understand these changes later.
Make the single one-line edit to get the desired functionality change.
This approach works just as well for changes to existing functionality as it does for adding new functionality, as everything is existing code after day 1. However, if you're branching in to a new area of functionality for your program, it may make sense to throw a quick-and-dirty implementation together to get real feedback on your plans.
There are many caveats:
If a deadline is looming, the risks of refactorings may outweigh the benefits. Judgement is required.
Sometimes the code would require extensive refactoring to make this work, but it would be possible to implement the desired feature or bug fix easily enough. In this case, I may do the more obvious, straightforward refactorings but not the ideal described above.
If I don't have high-quality automated tests, the risks of refactoring are more concerning. I may refactor less, depending on the circumstances. However, poorly-factored code is also difficult to unit test, so it's easy to end up in a quagmire if you're not careful.
Note that I avoid refactoring towards structure that I think will be beneficial for some future change that I can't be sure I'll need. Refactor for the issue at hand only. However, if this is not the first time I've needed to make this kind of change, I may broaden the scope of refactoring in anticipation of future similar changes. Judgement required, again.