jason if you sp_helptext sysmail_delete_mailitems_sp in the msdb database,

you'll see it's using a catch-all query to delete fromt eht able, and only one table;

after a bunch of error checking, this is the core of the proc:

DELETE FROM msdb.dbo.sysmail_allitems

WHERE

((@sent_before IS NULL) OR ( send_request_date < @sent_before))

AND ((@sent_status IS NULL) OR (sent_status = @sent_status))

i have this saved in my snippets for deleting old mail jobs, which deletes from two tables in msdb if you peek at the proc code.

USE MSDB;

GO

DECLARE @DeleteBeforeDate DateTime

SELECT @DeleteBeforeDate = DATEADD(d,-30, GETDATE())

EXEC sysmail_delete_mailitems_sp @sent_before = @DeleteBeforeDate

EXEC sysmail_delete_log_sp @logged_before = @DeleteBeforeDate

so you could do a simple DELETE:

DELETE FROM msdb.dbo.sysmail_allitems

DELETE FROM msdb.dbo.sysmail_log

as a proof of concept, i just did exactly that on my dev machine; cleared out 38K rows of stuff. no foreign key errors, just clean deletes.

hope that helps!