I was having problems purging my data using

exec sp_delete_backuphistory @oldest_date='1/1/2010'

in my msdb database, so I instead ran the following code to purge the data successfully

use msdb
ALTER TABLE [dbo].[sysmaintplan_log] DROP CONSTRAINT [FK_sysmaintplan_log_subplan_id];
ALTER TABLE [dbo].[sysmaintplan_logdetail] DROP CONSTRAINT [FK_sysmaintplan_log_detail_task_id];

truncate table msdb.dbo.sysmaintplan_logdetail;
truncate table msdb.dbo.sysmaintplan_log;

ALTER TABLE [dbo].[sysmaintplan_log] WITH CHECK ADD CONSTRAINT [FK_sysmaintplan_log_subplan_id] FOREIGN KEY([subplan_id])
REFERENCES [dbo].[sysmaintplan_subplans] ([subplan_id]);

ALTER TABLE [dbo].[sysmaintplan_logdetail] WITH CHECK ADD CONSTRAINT [FK_sysmaintplan_log_detail_task_id] FOREIGN KEY([task_detail_id])
REFERENCES [dbo].[sysmaintplan_log] ([task_detail_id]) ON DELETE CASCADE;

Then a normal shrink database solved it !

Enjoy