We had the identical situation occur using sp_delete_backuphistory on a 2.5 GB MSDB. Most of which was backup history.

Here's the way I've worked around the issue. Keep in mind that we blew away all history, because we simply don't use it, but you can augment the routine if you use backup history in any way. Then, you'll have to augment the code below to work for you.
 
Keep in mind this is not a Microsoft supported solution.

1.> To get started, get a base line of what's in those tables that you want to delete.

select count(*) from dbo.backupfile
select count(*) from dbo.backupmediafamily
select count(*) from dbo.backupmediaset
select count(*) from dbo.backupset
select count(*) from dbo.restorefile
select count(*) from dbo.restorefilegroup
select count(*) from dbo.restorehistory

2.> Now, Restore msdb to an alternate database. We restored to msdb1. Let SQL do it's thing unhindered by giving it msdb without your tinkering. You'll do the deletes on this database and then restore it back to msdb. Keep in mind that you don't want to create any new jobs that'll get erased when you restore this older, but smaller, msdb database.

3.> For the following tables check all the foreign key relationships and select cascade delete on every corresponding primary key.

Note, I tried to remove all relationships and truncate data from every table, but found that SQL would not let us add relationships back to the system tables. However, it will allow adding/removing the cadcade delete option.

4.> Once you're sure that you've added cascade delete to all those relationships, create a SQL job that runs the following statement.

use msdb1
delete from backupmediaset

5.> Run the job you just created and wait a while. Our delete took a little less than 3.5 hours for about 2.5 GB of backup history data.

6.> Let the job complete, backup msdb1, and restore to msdb.

I ran the following statements to oust connections to msdb so we could restore it. (lines are wrapping here)

alter database msdb set restricted_user with rollback immediate
go
RESTORE DATABASE [msdb]
FROM DISK=
's:\msdb1.bak'

WITH REPLACE,
move 'MSDBData' TO 'R:\Program Files\Microsoft SQL Server\MSSQL$I2KMCDC1\Data\msdbdata.mdf',
move 'MSDBLog' TO 'R:\Program Files\Microsoft SQL Server\MSSQL$I2KMCDC1\Data\msdblog.ldf'
Go

7.> After the restore, you'll notice the job you created to run the delete, disappears and that your msdb mdf file is much, much, smaller.

8.> Run the following to verify:

select count(*) from dbo.backupfile
select count(*) from dbo.backupmediafamily
select count(*) from dbo.backupmediaset
select count(*) from dbo.backupset
select count(*) from dbo.restorefile
select count(*) from dbo.restorefilegroup
select count(*) from dbo.restorehistory

9.> Remove all the cascade deletes from the backup/restore table relationships in msdb.

10.> I'm going to try to run sp_delete_backuphistory on a regular basis instead of waiting so long. Hopefully, we won't have to do this again.

***Keep your old original msdb backup copy around for a few weeks in case you discover any anomalies.