Just wanted to add that I found a few event log entries that go along with the queue error:

Event Type:      Warning
Event Source:      EXCDO
Event Category:      General
Event ID:      8230
Date:            1/23/2008
Time:            9:57:31 AM
User:            N/A
Description:
An inconsistency was detected in User@Domain.com: /Calendar/FW%%3A Meeting.EML.  The calendar is being repaired.  If a problem persists, please recreate the calendar or the containing mailbox.

&

Event Type:      Error
Event Source:      EXCDO
Event Category:      General
Event ID:      8206
Date:            1/23/2008
Time:            9:57:31 AM
User:            N/A
Description:
Calendaring agent failed with error code 0x80040215 while saving appointment.

&

Event Type:      Error
Event Source:      EXCDO
Event Category:      General
Event ID:      8213
Date:            1/23/2008
Time:            9:57:31 AM
User:            N/A
Description:
Calendaring agent failed to update the free/busy cache during an appointment save or delete operation.

&

Event Type:      Error
Event Source:      EXCDO
Event Category:      General
Event ID:      8199
Date:            1/23/2008
Time:            9:57:31 AM
User:            N/A
Description:
Calendaring agent failed in message save notification with error 0x800703eb on User@Domain.com: /Calendar/FW%%3A Meeting.EML.

Thanks!

this article talks about this issues specifically

http://technet.microsoft.com/en-us/library/bb887638.aspx

Thanks for the info Zanemwest. I've seen this article before, but we have not changed the log on information at all. Just for the heck of it, I went ahead and tried re-selecting the network service, but it had no effect. The message is still stuck.

i have dpone some more checking and typically event id has something to do with virtual machines, some other references point to the machine acount being out of sync.
use netdom to resync this.
there was also some references to the service account having trouble but specifically the iis service account.
the more i look at it the commonality between all these semes to be a security issue of some kind most of the time it seems to occur after a abnormal reboot of the server.

this one also looks promising although it is exchange 2003

http://support.microsoft.com/?id=310440

This states that the error is as a result of file level AV scanning on the exchange server, so i have to ask do you have an AV running on the server and have you excluded the exchange directories for the database files and log files from the scan

http://www.eventid.net/display.asp?eventid=8230&eventno=2901&source=EXCDO&phase=1

I have verified the MSExchangeFBPublish key does exist in the registry and it appears to be correct.

The EventID page seems to fit the problem we're having almost exactly, but we are only running Symantec Information Foundation Mail Security for Microsoft Exchange Version 6.0.3.201 right now. We are not running any file-level AV at the moment.

Thanks for all of the ideas.

darkstar3d, I tried moving the mailbox to another storage group, but that had not effect. I'll try deleting and readding a mailbox a little later.
Thanks for the suggestion.

The EventID page that Zanemwest posted suggested AV might be the problem, so I'm also downloading the newest version of Symantec's Exchange AV software, v6.0.4.209. I guess we'll see if that makes any difference.

Thanks Zanemwest and darkstar3d! I deleted one of the mailboxes and recreated it and the messages went through just fine. The weird thing is that it is only happening when inviting attendees for calendar events. I guess I'll just have to recreate all of the ones that were having the problem.
Thanks for all of your help!

Thanks guys.