Removing Database Backup History

The msdb database stores (amongst other things) the history of backups performed on the sql instance.
Once a backup has been archived, i.e. moved away from the location it was originally written to, there is no need to keep the record of the backup. Infact, these records build up, increasing the size of the msdb database (quickly if frequent transaction log backups are performed).

To see the date range of backup history you have, us this query -

use msdb
SELECT 
  a.name
, MIN(b.backup_finish_date) EarliestSuccessfulBackup
, MAX(b.backup_finish_date) LatestSuccessfulBackup
FROM master..sysdatabases a
LEFT OUTER JOIN msdb..backupset b ON a.name = b.database_name
GROUP BY a.name
ORDER BY a.name

To prevent this occuring, use system stored procedure sp_delete_backuphistory and pass it the date of the oldest record you want to keep.

use msdb
go
exec sp_delete_backuphistory '1/1/2006'

If a database is removed altogether, zap it's backup history like this -

exec msdb.dbo.sp_delete_database_backuphistory 'Adventureworks'

If backups are archived regularly, schedule a job to remove excess history records, like this -

-- Calculate date to be used when removing records,
-- This example deletes records over a month old.
DECLARE @dtOldest_date DATETIME
SET @dtOldest_date = dateadd(month, -1, getdate())
EXEC msdb..sp_delete_backuphistory @dtOldest_date

NB :SQL 2005+ addresses this by providing cleanup tasks in the Maintainence Plans (if you use them).