I think you can just add their old surname's email addresses as aliases on the new LDAP account. We use those addresses to determine what emails to show to end users. If that doesn't work, it's usually worth calling in to support. That way we can check exactly what the Barracuda Message Archiver is searching for, and then what exactly is in the LDAP account, and we can compare to find the discrepancy.
Technical Delivery Manager