Thanks for a bug report. Could you write some steps, say since start of evolution, how to reproduce this issue, with compare of steps which leads to working completion from your EWS GAL, please? I suppose this GAL comes from evolution-ews.

1. Login
2. Launch evolution
3. Compose Message
4. Try fill receiver field

Yes, I am talk about EWS, but same problem exists when I use MAPI.

Aah, you meant when you "try to fill To address", with autocomplete. I was confused by the bug summary, because it reads "I filled".

Bug #828321 is filled for evolution-mapi, there usually help to restart (just close) evolution-addressbook-factory process, but I still didn't find what can be wrong there. If the same is reproducible with evolution-ews, especially, if after login it's enough to close evolution-addressbook-factory process and let it run a new one, then the issue is somewhere else than in evolution-mapi. Could you try that, please? It might be like this:
a) login
b) do not run evolution yet
c) open terminal, check for running factory with command:
   $ ps ax | grep evolution-addressbook-factory
d) kill the factory process
e) run evolution
f) try autocomplete the address in To header

a) login
b) do not run evolution yet
c) open terminal, check for running factory with command:
   $ ps ax | grep evolution-addressbook-factory
d) kill the factory process
e) run evolution
f) try autocomplete the address in To header

yes, this is workaround problem

Thanks for testing this. From your findings I believe this is neither evolution-mapi, nor evolution-ews issue, but something much deeper, like wrong order of service run, when the addressbook factory doesn't have running other services it needs (the one for passwords comes on my mind), or something like that. I'm marking this as a duplicate of the older bug and I'm upstreaming it.

*** This bug has been marked as a duplicate of bug 828321 ***