Just had an issue running sp_delete_backuphistory where the stored procedure would never complete (we left it run overnight). The stored procedure hadn't been run in a while on this server so the backupset and related tables were quite large (over 100,000 rows), after looking at the source of this stored procedure I have two comments/questions:

1. Why does this stored procedure use a cursor? As far as I can tell there is nothing in it that couldn't be done in set operations.

2. Why aren't there any useful indexes on the backupset table? Simply adding an index to backup_finish_date improved the speed of this stored procedure a huge amount.