I now think the only way transition to MD5 auth, without tearing down existing adjacencies, is to simply beat the HELLO and DEAD timers when configuring the authentication key on all the routers participating in the process. I had to put the MD5 key on the interfaces before their DEAD timers expire, with enough time to transmit another HELLO.
But if you already have authentication enables, then it trivial to change keys:
It seems that MD5 Auth uses a non-destructive 'rollover' process.
The system assumes its neighbors do not have the new key yet, so it begins a rollover process. It sends multiple copies of the same packet, each authenticated by different keys. In this example, the system sends out two copies of the same packet--the first one authenticated by key 100 and the second one authenticated by key 101.
Rollover allows neighboring routers to continue communication while the network administrator is updating them with the new key. Rollover stops once the local system finds that all its neighbors know the new key. The system detects that a neighbor has the new key when it receives packets from the neighbor authenticated by the new key.
After all neighbors have been updated with the new key, the old key should be removed. In this example, you would enter the following:
interface ethernet 1
no ip ospf message-digest-key 100