Robert,
If an issue is this urgent you really should be creating a case with support to help you diagnose where these issues may lie.
So just a quick couple of things however
What storage are you using?
(Could there be a network problem, or storage problems leading to the slowness?)
How are you gauging the amount of items deleted?
Are you using NTFS Collections?
(If you expire or delete items that are collected into a cab, only the record is removed from the database, the CAB file and the items in the cab file will remain until there are too few items to consider keeping the CAB file around, and a process called Sparse collections kicks off)
Are you getting any deadlocks or blocking on the SQL Server?
Sometimes you may find that in the activity monitor of SQL that expensive SQL Queries are blocked due to disk queue lengths, this can usually be remedied by SQL maintenance, seperating logs from the databases on to different drives etc.
Are the indexes healthy?
Use IndexVolumeReplay or the inbuilt index volumes in the vac in 2007 to see if the indexes are online and operational, part of the expiry process is to first remove them from the index, so if there are issues reading or writing to the index this may slow things down considerably
Also what SQL query did you run saying that you had items to delete?
Ultimately you will should create a support case, but what would help considerably is if you get a DTrace of the StorageDelete process, and have this ready for the support engineer to diagnose, this will show on a very granular level the length of time its taking to remove records, show any slow SQL queries etc
cheers