This is another request for EWS contain class/message class information.
It turns out that if you delete a contact, I also would guess it applies to a task, appointment, etc., the items in the deleted folder are a mix of message types. Trying to fetch the messages from the deleted folder when there are mixed messages will result in "MIME conversion is not supported for this item type" for all messages that are not of the "IPM.Note" class.
It would be extremely helpful to have the message class in the ExchangeMessageInfo.
Thank you for considering this.