Como posso corrigir "Não é possível executar um backup diferencial ... um backup de banco de dados atual não existe"?

Recentemente, mudamos para o FULLmodelo de recuperação, com backups completos sendo feitos todo fim de semana e diferenciais sendo feitos todos os dias.

O problema é que os backups diferenciais nem sempre parecem funcionar. A mensagem de erro registrada no histórico do trabalho é

Executado como usuário: nome de usuário. ... 9.00.3042.00 para 32 bits Copyright (C) Microsoft Corp 1984-2005. Todos os direitos reservados.
Iniciado: 11:20:12 AM Progresso: 2013-01-25 11:20:13.90 Fonte: {450389BA-54C2-4892-9CD0-0126CA9B0ED8} Executando a consulta "DECLARE @Guid UNIQUEIDENTIFIER EXECUTE msdb..sp".: 100% complete End Progress Error: 2013-01-25 11:20:14.40 Code: 0xC002F210
Source: Back Up Database (Differential) Execute SQL Task
Description: Executando a query "BACKUP DATABASE [MyDatabase] TO DISK = N'E:\Database Backups \MyDatabase_backup_201301251120.diff' WITH DIFFERENTIAL , NOFORMAT, NOINIT, NAME = N'MyDatabase_backup_20130125112014', SKIP, REWIND, NOUNLOAD, STATS = 10 " falhou com o seguinte erro:"Não é possível executar um backup diferencial para o banco de dados "MyDatabase", porque um backup do banco de dados atual não existe. Execute um backup completo do banco de dados reemitindo BACKUP DATABASE, omitindo a opção WITH DIFERENTIAL. BA... A execução do pacote fa... A etapa fracassado.

A tarefa de backup completo é sempre concluída com êxito e posso visualizá-la msdb.dbo.backupsetusando a consulta encontrada aqui , então sei que ela existe. E parece que após uma reinicialização, o backup diferencial é concluído com êxito até o próximo backup completo.

Aqui está uma olhada no histórico de trabalho que tenho:

1/16 - Backup completo - Sucesso
17/01 - Backup Diferencial - Sucesso
18/01 - Backup Diferencial - Sucesso
19/01 - Backup Diferencial - Sucesso
1/20 - Backup completo - Sucesso
21/01 - Backup Diferencial - Falha
21/01 - Backup Diferencial - Falha
1/22 - Backup Completo - Sucesso
1/22 - Backup Diferencial - Falha
22/01 - Reiniciar
23/01 - Backup Diferencial - Sucesso
23/01 - Reiniciar
24/01 - Backup Diferencial - Sucesso
25/01 - Backup completo - Sucesso
1/25 - Backup Diferencial - Falha

As reinicializações ocorreram devido a um erro não relacionado onde @@SERVERNAMEestava null, então adiei postar esta pergunta até descobrir se a correção do @@SERVERNAMEproblema foi corrigida, mas não resolveu e agora não tenho ideia por onde começar.

O que pode fazer com que o SQL Server não reconheça um backup completo de um banco de dados e como posso corrigi-lo?

Também não tenho certeza se isso está relacionado, mas os backups diferenciais parecem bastante grandes e estou me perguntando se eles estão executando o diferencial do backup completo do banco de dados feito no início (em 16/01) em vez do mais backup completo recente. Os backups completos são de cerca de 260 GB e os diferenciais de 23/01 a 24/01 são de 30 GB cada.

Os trabalhos foram configurados usando o SQL Server Maintenance Plan Wizard e estou usando o SQL Server 2005

O botão [View T-SQL] para o plano de manutenção retorna este código:

Backup completo:

BACKUP DATABASE [MyDatabase] 
TO DISK = N'E:\Database Backups\MyDatabase_backup_2013_01_25_140607_2543780.bak' 
WITH NOFORMAT, NOINIT, SKIP, REWIND, NOUNLOAD, STATS = 10, 
    NAME = N'MyDatabase_backup_2013_01_25_140607_2523778'

Diferencial:

BACKUP DATABASE [MyDatabase] 
TO DISK = N'E:\Database Backups\MyDatabase_backup_2013_01_25_140537_4073936.diff' 
WITH DIFFERENTIAL, NOFORMAT, NOINIT, SKIP, REWIND, NOUNLOAD,  STATS = 10, 
    NAME = N'MyDatabase_backup_2013_01_25_140537_4053934'

_{Isso está muito relacionado a outra pergunta que tenho , no entanto, foi sugerido no chat que eu postasse uma nova pergunta em vez de editar a outra devido às perguntas serem diferentes e às respostas existentes na outra pergunta.}