The item could not be deleted. It was either moved or already deleted...

It seems upon further testing that it's any mailbox (mine, or shared mailboxes) I set my Microsoft Outlook to access.

With the exception of my mailbox (which gives me this error both in Outlook and Outlook Web Access) I can't delete any mail from any mailbox that I add to Outlook, but can log into Outlook Web Access and do it. This one has me totally stumped here.

Have you recreated the Outlook profile?
If you are using Outlook 2003 in cached mode then that is almost certainly the cause.

Simon.
Exchange MVP.

I have, no luck.

I didn't think that would be it though, since it's also affecting Outlook Web Access.

Another weird thing to note...

I opened an old backup .pst folder in Outlook and moved several E-Mails from it to the mailbox on the server. They moved successfully, but once moved I couldn't delete them. I was able to move them back, for whatever it is worth...

Sorry for the back-to-back posting, but I discovered something else.

I'm able to move E-Mails out of the Exchange mailbox, to an offline .pst for example. It just seems that I can't delete or move within the Exchange mailbox.

Even though you didn't change the mailbox rights...it's possible that the rights may have gotten corrupted on this mailbox when you ran eseutil.  In Active Directory Users and Computers go to the properties of your user account.  On the Exchange Advanced tab you can check the mailbox rights.  Just verify that everything looks good there.  That would be the first step.

Already done, but thank you for trying.

It's definitely something wrong the with my Active Directory profile or Exchange mailbox. I set up a new Outlook profile with a shared mailbox (not my primary mailbox) and can freely delete things. I guess the next step would be to just kill the mailbox and restore from a .pst that I luckily had made that very morning.

To complicate matters I was able to set up an Outlook profile with access to a shared mailbox, and open my mailbox by going under "File/Open/Another User's Mailbox", and was freely able to delete things then. This is so very strange...

Wow, yeah that's very strange.  I would definitely recreate the mailbox.  Either of the methods for getting your old data into the new mailbox would be fine.  Good luck...sometimes things just get FUBAR.  :)

Well, deleting the mailbox and restoring from the .pst worked perfectly.

Strange.

Here's your points; thanks for helping.

No problem...definitely a weird thing.  Thanks.

I know that this is late since you seem to resolve the issue, but here is my 2 cents worth.

When ESEUTIL /P is run against a database, it must always be followed by an ISINTEG -FIX.
The reason is that ESEUTIL works on the page level of the database. The database is written in 4 KB pages. If there is a corrupted page it will try to fix it. If it cannot be fixed, it will be deleted.
ISINTEG works on the integrity and links between the tables in the database.

I have seen your issue many times in the past when ISINTEG was not run after ESEUTIL /P. ESEUTIL deleted a page or pages in the database yet the tables in the database still referenced this deleted page, hence the error you were getting.

Hope this helps in the future.

I'm having the same problem.
Can I run ISINTEG on its own (at any time)
Or is it reccomended that ESEUTIL is run them ISINTEG?

KiethC - this is an old question. Unlike a forum it is not possible to "bump" questions back up the list. The only people who will see your post are those that have already participated. Instead you should post your question as a new question in the Exchange Server Zone which will allow other experts the chance to see the question and respond.

Simon
Exchange Server Zone Advisor.

I know this is very old, but I was able to fix this error using Exchange_Admin's comment regarding isinteg.  

I dismounted the Exchange databases  and ran this command:
isinteg -s <SERVERNAME> -fix -test alltests

Also this was an Exchange 2007 machine.