We had an EDB from another organization that we needed some messages from. I used a 3rd party tool Lepide Exchange Recovery Manager to export the messages to a pst and then imported them to the Exchange 2010 mailbox.
The messages are there and look fine, but when replying to one it throws the above error. After searching I've found a lot of posts regarding X500 and LegacyExchangeDN, but the kicker here is that this is being replied to an external user NOT internal so that shouldn't be an issue. It does this from OWA and Outlook so it isn't an autocomplete issue either.