Lowell,
I actually just stole your code, pretty much word for word. Below is the Agent Job step 1 I'm using:
use msdb
go
declare @DeleteToDate datetime()
set @DeleteToDate = DATEADD(d, -30, getdate())
DELETE FROM msdb.dbo.sysmail_allitems
where sent_date < @DeleteToDate
DELETE FROM msdb.dbo.sysmail_log
where log_date < @DeleteToDate
delete from msdb.dbo.sysmail_mailitems
where sent_date < @DeleteToDate
Then step 2:
use msdb
go
dbcc shrinkdatabase(N'MSDB')
go
USE [msdb]
GO
DBCC SHRINKFILE (N'MSDBData' , 0, TRUNCATEONLY)
GO
As for the rest of the space, it's still in sysmail_mailitems and I suspect the reason for it is the body column. The manager who uses DBMail to send out stuff, is sending some HTML e-mails, so I suspect those are taking up a good bit of space in the table. Thankfully, the server isn't tight on disk space, so I can live with a 23-24GB DB.
Once more, thanks!
Jason