How to move a MKAnnotation without adding/removing it from the map?

Just use KVO:

[annotation willChangeValueForKey:@"coordinate"];
[annotation didChangeValueForKey:@"coordinate"];

If your MKAnnotation has an setCoordinate method, just include these lines right there:

- (void)setCoordinate:(CLLocationCoordinate2D)newCoordinate {
    [self willChangeValueForKey:@"coordinate"];
    coordinate = newCoordinate;
    [self didChangeValueForKey:@"coordinate"];
}

Don't know whether it's more generally possible, but it is if you have your own custom MKAnnotationView.

I was able to adapt the approach documented at http://spitzkoff.com/craig/?p=108 by Craig Spitzkoff:

1. Give your custom MKAnnotationView a reference to your MKAnnotation object
2. Add an updateCoordinates method to the MKAnnotation object and call it when you want to change location of the annotation
3. Call regionChanged on the custom MKAnnotationView to let it know when to reposition itself (e.g. when MKAnnotation has updated coordinates)
4. In drawRect on the internal view object owned by your custom MKAnnotationView you can reposition using the coordinates of the MKAnnotation (you're holding a reference to it).

You could likely simplify this approach further - you may not require an internal view object in all circumstances.

If you keep a reference to your annotation, make a change to the coordinate property, then add the annotation to the map again, the location of the annotation view will update. You do not need to remove the annotation (which will cause the annotation view to momentarily disappear). This will not give you a nice transition for when the annotation coordinate is updated however. It also does not result in a memory leak nor are there a multiple of the same annotation added to the map (if you look at the number of annotations on the mapview, it remains constant when you re-add the annotation).

It doesn't seem possible to change the coordinate of a MKAnnotation object and then inform the MKMapView of the change.

However, removing the previous annotation from the map, changing the coordinate of your annotation object and adding it back to the map works well.

[theMapView removeAnnotation:myAnnotation]; 
[myAnnotation setLatitude:newLatitude];
[theMapView addAnnotation:myAnnotation];

Why don't you want to do it this way?