Eu também tive esse problema; a solução é bem simples. No seu iPhone, vá para "Configurações > Mail, Contatos, Calendários" e role para baixo até a seção Contatos. Altere a configuração "Conta padrão" de "No meu iPhone" para o seu servidor Exchange. Isso garantirá que os contatos criados a partir de um e-mail ou de uma mensagem de texto sejam sincronizados com o Exchange.