Ok, here we go.
So my A/V got an update but there was a bug with the update. The Exchange agent went through our mailstore and started marking old .doc files as trojans and replaced the document file with a txt file. I was trying to recover the original document file...I still had the old email.
In 9.1 it's hard to tell which message you are restoring if they all have the same subject. I have about 8 messages with the same subject but only some of them have attachments. I was restoring all of the files into their original location and realized that even though according to Outlook I have 40+ messages in that folder, BE only had about 22 messages. Some of those missing messages where the ones I was attempting to recover. I choose the 8 messages in BE with the correct subject but really there were about 12 messages with that subject.
Long story short it was working the whole time, I just didn't know it because the files I wanted back are showing up in BE.