Whats is this format called? "/o=First Organization/ou=First Administrative Group/cn=Recipients/cn=user"

It's called legacy Exchange distinguished name and is a remnant from Exchange 5.5.

You can either resolve this address using the ResolveNames method (http://msdn.microsoft.com/en-us/library/exchangewebservices.exchangeservicebinding.resolvenames(v=exchg.140).aspx) of the EWS Managed API, call the EWS WebService method ResolveName directly.

Another option is to use LDAP and search for the user object with the property legacyExchangeDN set to your address. Then, query the proxyAddress attribute and retrieve the one address which is prefixed with "SMTP:" (all uppercase).

The method Henning's link is deprecated with Exchange 2013.

Now the recommended way is to do it through ExchangeService.ResolveName() and retrieve the STMP address from the Mailbox property.

public string ResolveToSmtpAddress(string address)
{
    try
    {
        NameResolutionCollection nrc = _service.ResolveName(address);

        foreach (var add in nrc)
        {
            return add.Mailbox.Address;
        }
        return null;
    }
    catch (Exception)
    {
        throw;
    }
}