Como sugerido acima, eu transformei meu "Edit" em uma resposta.
O que funcionou para mim foi permitir que o Adobe Reader se conectasse à Internet (o mais complicado era eu oscilar entre o proxy e nenhum proxy no trabalho e em casa e, normalmente, como sou preguiçoso, só defino o proxy no Firefox, mas não no sistema (Windows 7), que é o que a Adobe usa para o Reader). Depois disso, no dia seguinte, não houve mais problemas.
Depois disso, e iniciar o Adobe Reader, você ainda verá o congelamento, mas apenas por cerca de 0,3 s, enquanto recupera o que está procurando na rede. Eu ainda não tenho absolutamente nenhuma idéia do que exatamente esta rotina da web está fazendo e por que ela tem que causar um congelamento completo do Reader enquanto conta o tempo limite quando não há conexão com a Internet. A sugestão de chokingyou parece certa, embora eu não pudesse testá-lo na minha configuração e verificá-lo, já que não tive mais o problema.
É por isso que marquei minha resposta como a resposta escolhida e fitei sua resposta para aqueles que querem saber a verdadeira (e provável) causa final do problema.