I used to go back and edit my Mercurial commits to try to create a pretty history. I might have put two unrelated things into one commit, or I might have made several commits that were better understood as a single commit, but eventually it seemed like a waste of time and I got over the minor embarrassment of having less than perfect history.
Do you still do this? Why is it worthwhile to you, why don't you do it anymore, did you ever do this, or are you thinking of starting?
If I was contributing to the Linux kernel this would obviously be worth my time because Linus would reject my patch otherwise, but IMO one of the big mistakes of dvcs users is to imagine their project is like the Linux kernel. My projects usually only have a few developers.
It is not worth the effort.
So long as 'tip' is pretty, you're better off letting history be ugly and accurately reflect how the work came about, rather than how you wished the work came about.
When I'm digging through history half the time I'm asking "what did this used to look like?" but the other half of the time I'm asking "why did this end up looking like this" and I want to see the developer's abortive attempts even if he'd rather erase the fact that he ever tried to go down a path that didn't pan out.
I make an effort to clean up my revision history. My workflow goes along the lines of make a small but meaningful edit, commit, repeat until some series of larger modifications are made. Then I go back and re-order/group commits together into functionally atomic commits, and push those revised commits out. This allows other developers to see commits which create functional differences, as opposed to massive walls of trivial commits. Makes it easier to debug regressions when they occur.
I'm trying to remember that commit comments will appear in the annotate view later. Therefore I'm trying to explain intent and overall effect of the committed changes but not the change itself.
If you only append to the history and look at the latest version, it doesn't matter for you.
I recently was working on a project where someone did a "merge" by applying a large patch across two branches. I found it by looking for a change that introduced a feature to see what tests came along with it. Wasted lots of time.
You'll also see that the new dimension that merges introduce makes bisection a lot more difficult. It's no longer just left or right.
If it is an application that can be expected to go back and forth between revisions, such as branching from older revs to maintain different versions, I would consider having clean and accurrate commit messages to be a valuable tool to the project.
If you are just working on incremental updates with little possibility of breaking the build on rare conditions, I wouldn't bother too much on them being extremely accurate.