Question: Editing Scanned Maps with Software?

Recently I’ve received a couple of very similar questions: both are from people asking how to edit and manipulate scans of paper maps.

Chris Ellison writes,

I am a history teacher who regularly uses maps for teaching purposes. The thing is, I always wish I could add an extra arrow or that I could erase a distracting feature, or remove a modern adaptation. Is there any simple(ish) software where I can take a scanned map and make adaptations (change the scale, add and remove features, add or remove colors)? Perhaps there is a commonsense approach to this, but I don’t know it. Thanks in advance to you or your readers for any advice.

And Ed Brumby writes,

I’m completely new to drawing maps. I want to edit a 1780 map that has sort of contour lines that look like shading. I am using Adobe illustrator. How do I do this?

The problem to me seems to be the difference between a scanned image, which is a single-layer bitmap, and an Illustrator or Photoshop file, which can have each element on a separate layer and, in Illustrator’s case, is vector data rather than a bitmapped image. My guess is that any amount of editing an old map is essentially akin to photoretouching: you’re blotting out old features and adding new ones on top; editing scale and other features is essentially trying to manipulate GIS layers that simply don’t exist in a scanned image.

Is there a solution here? What can you do with a scanned image?