Answer to original question.
She has a warehouse full of servers to which a /28 range of public ipv4 space is routed (call it the W.X.Y.Z network).
The smallest allocation that can be routed on the public internet is a /24, so this /28 must be a sub-allocation from an ISP. To have a business operation that justifies a "warehouse full of servers" and yet be reliant on a tiny block of IP addresses allocated by an ISP was very foolish of her.
I would imagine that Alice could simply move her machines, and eventually the routing protocols will rediscover that W.X.Y.Z is in California rather than Maine.
Your imagination is far from the reality.
Since Alice's block is allocated by her ISP she is at their mercy. If her ISP has a presence in California, they may be able to move the addresses to a link they provide there. They may be reluctant to do this though as it will complicate their internal routing, and it may well result in sub-optimal routing for her traffic.
If she can't get her ISP to help she is going to be stuck with maintaining some level of presence in Maine and renting a link (or setting up a VPN) from Maine to California.
If Alice instead had a provider-independent /24, she could stop advertising it to her provider(s) in Maine and start advertising it to her provider(s) in California. Unless you are a major network yourself, your providers will probably require evidence of IP block ownership before accepting your advertisements for it. If the provider is smaller, they may have to pass that evidence on to their providers.
Between the major networks, maintaining filter lists starts to get rather impractical. So things generally work on trust. This does cause problems sometimes when a network violates said trust and lets in routes that they should not have.
In order to provide consistent service to her clients, she cannot change the addresses (but her clients accept their sites being down for a few days as they are moved to CA).
This seems unlikely. In the real world alice would almost certainly have to set up some kind of private link for the duration of the migration so that the servers could be moved in smaller blocks with internal re-routing on alice's network.
Here's the problem: evil Bob moves into Alice's warehouse and sets up servers which claim to neighboring machines that they are the W.X.Y.Z network.
Alice should terminate any services she has in her old premises before moving out. If Bob moves in and wants connectivity then it's up to him to negotiate that with providers.
Of course if Alice gives up the IPs as part of terminating said services, then the ISP could reallocate them to bob, that is a risk you take when using provider allocated IPs.
Answer to updated question.
Comcast is moving the W.X.Y.X/28 network from Vermont to California. Eventually the routing protocols will let COX routers in Kansas know that they need to send packets westward instead of eastward.
COX won't know about W.X.Y.X/28. The longest prefixes in the Global routing table are /24s, but prefixes advertised by large ISPs are generally shorter than that.
If an ISP wants the flexibility to move small blocks around the country then they will need to deal with that in their own network.
For larger blocks the ISP can advertise them seperately on the Internet and there can be some advantages to doing so.
How long will it typically take for the network to update itself in this manner?
Generally a route in the global routing table will propagate within a few minutes. If the rules in place allow it.
For the most part though, the internet doesn't care much about where a destination actually is, just what networks it can be reached through.
Large providers will typically run a single large network and will advertise all their prefixes to their upstreams and peers from all locations, though they may sometimes put in place multi-exit discriminators or as-path prepends to influence which exit is chosen.
Comcast is moving the W.X.Y.X/28 network from Vermont to California. Time Warner Cable decides that this is a good opportunity to try to expand their empire into Vermont. (I know TWC would not actually try to do this. I do not have anything against TWC, I am simply using them as an example.) They set up servers in Vermont which advertise to the network that they are part of the W.X.Y.X/28 network.
Ignoring the fact that a /28 is too long a prefix to advertise on the Internet. If Charter (formerly TWC) started advertising comcast address space then it is very likely they would end up receiving some of the traffic that was destined for Comcast. Comcast would NOT be happy about this.
The relationships between the big networks work on trust. Mistakes do happen but they are generally rectified quickly.
What would happen if a major provider started systematically hijacking address space I do not know. I would expect lawsuits to start flying pretty quickly as well as a bunch of extra filters to be put in place at various upstreams and peers of the offending provider.
In this case, COX routers in Kansas will have no way of knowing if the legitimate W.X.Y.X/28 networks lies westward or eastward.
The internet does not work in terms of "westward" and "eastward", it is not some huge mesh of local links. There is not some big common backbone. Each provider has their own network or networks which interconnect with each other as the buisinesses see fit.
Providers generally care far more about who you are than where you are. Whatever rules COX apply to advertisements from Comcast, they will likely apply the same rules at all the locations where Cox and Comcast interconnect.
What does Comcast have to do in order to notify the other ISPs of the geographic change of their W.X.Y.X/28 network.
Nothing, the only routers that need to know the exact geographic location of W.X.Y.Z/28 are those in comcast's network.
