I have never liked how every undiscovered map marker is 100% accurate on the map and would find game play more interesting if all undiscovered locations (except for cities/towns) be in the general area of location but not accurate. Once discovered by the player the incorrect undiscovered map maker updates to the discovered map marker location. Is something like this even possible in Skyrim and how it handles the map makers?

I'm not sure. Have a simple script do a 'MoveTo' on a map marker and see if it moves it on your map or not. If so, you can work on a way of detecting when the player discovers it (IsDiscovered or something like that is a function I believe?) and then you can move it.

Yes, it's possible. I'm not sure of the exact method to do it, but Dawnguard does this with the map marker for Fort Dawnguard.

When you set a map marker, you can link a reference to it. With a linked ref, you fast travel to where the linked ref is located. Just have a script update the linked ref to point to a different target once you've discovered it.