Error: "ERROR: GetProps: [80004005] Unspecified error Error: The client operation failed. Low lev (4270952)

Lots of ESM errors in the Eventlog.
Checking the log mentioned in the Eventlog message shows the following:

07:29:32 DEBUG: BEGIN WalkMessage(Re:Your Message) in folder 'Deleted Items'
07:29:32 DEBUG: BEGIN GetCheckSum()
07:29:32 DEBUG: calling GetProps for property 007D001F
07:29:32 ERROR: GetProps:
07:29:32 [80004005] Unspecified error
07:29:32 Error: The client operation failed.
07:29:32 Component: Microsoft Exchange Server Information Store
07:29:32 Low level error: 80004005
07:29:32 Context: 00000501