First of all has the server been rebooted in that time?
I have seen that happens when AV software has got hold of the files and will not release them.
Instructions to delete messages from queue:
1. Click Start, point to All Programs, point to Microsoft Exchange, and then click System Manager.
2. Double-click Servers, double-click the server that you want, and then click Queues.
Note If you have administrative groups defined, double-click Administrative Groups, double-click Administrative_Group_Name (where Administrative_Group_Name is the group that contains the queue you want), double-click Servers, double-click the server that you want, and then click Queues.
3. Right-click the queue that you want to modify, and then click Freeze to freeze the queue.
4. Click Find Messages, and then click Find Now to find messages in the queue.
5. Right-click the message that you want to delete, and then click one of the following options:
• Click Delete (no NDR) to delete messages from the queue without sending a non-delivery report (NDR) to the senders.
• Click Delete (with NDR) to delete messages from the queue and send an NDR to the senders of the messages.
Note To delete several messages that are next to each other, click the first message, hold down SHIFT and click the last message, right-click one of the selected messages, and then click either Delete (no NDR) or Delete (with NDR). To delete several messages that are not next to each other, click the first message, hold down CTRL and click additional messages, right-click one of the selected messages, and then click either Delete (no NDR) or Delete (with NDR).
6. When you are prompted to delete the messages in the queue, click Yes.
If this does not work…
If you don’t have any legitimate messages in the queues, turn the timeout down on the SMTP server, which will flush them out quickly.
Then check your server for possible security issues.