Perguntei por aí e encontrei a resposta!
A sincronização é um mecanismo para troca de dados entre clientes (normalmente, instâncias do Firefox). Não é um armazenamento persistente na nuvem e não é um serviço de backup. Ele não tem necessariamente todos os seus dados (por exemplo, o histórico antigo não é enviado) e não é garantido que você fique por aqui.
Há também eventos que deliberadamente apagam o servidor - uma atualização de versão de armazenamento (como ocorreu entre b7 e b8) é uma delas. Uma limpeza é uma circunstância não excepcional; os clientes simplesmente farão o upload novamente.
Então, quando tentei me conectar para sincronizar logo após instalar o FF novamente, algo deu errado por algum motivo desconhecido. Quando atualizei para o FF4 b8, todos os meus dados de sincronização foram apagados!
Estou usando a sincronização de FF e X-marks agora, além de fazer backups mensais dos meus favoritos novamente!