In a few months we'll be switching providers.
Any ideas are welcome.
Moving them one at a time would probably be the easiest solution. That way, while you're waiting for the old address of the server that was moved to time out of caches, the one that stayed put will still be reachable. After that address change has propagated, you can then move the second server, and while its old address is still in caches the server that was moved first will be reachable. However, you should reduce the TTLs of the records for all the machines in your domain whose IP addresses will be changing as a result of the move. This record has nothing to do with how long it takes for old records to expire, that's what TTL is for.