SQL 2005 Database Backup History Returns Incorrect Physical Device

Issue
After removing a backup device and re-creating the device on another drive, I ran a query to determine the last backup for each db on SQL Server (query link below).  The physical backup location still returned the old device file as the last backup location.

Reference Info
The query I use to check the latest backup for databases on a SQL Server was downloaded from mssqltips and is customised depending on the environment.
http://www.mssqltips.com/tip.asp?tip=1601

The script returns valuable backup information on a per database basis, using the following system tables:

dbo.backupset:  provides information concerning the most-granular details of the backup process

dbo.backupmediafamily:  provides metadata for the physical backup files as they relate to backup sets

dbo.backupfile:  this system view provides the most-granular information for the physical backup files

Troubleshooting
On investigation, msdb..backupmediafamily still had the 'old' value for physical_device_name. 

I tried dropping and recreating the backup device, but this did not fix the issue.

Fix
I took  a backup of msdb to retain the old backup information and executed the following system sproc to remove backup history:
 exec msdb..sp_delete_database_backuphistory '[DBName]'

After the next backup, the physical device name returned as expected.

Applies To (in this instance)
SQL Server 2005 9.0.4053