O que realmente está sendo procurado é a capacidade de pesquisar no servidor e armazenar em cache localmente os endereços de e-mail de preenchimento automático. O aplicativo da web do Gmail e o aplicativo de e-mail do Windows Phone fazem isso. Windows Mail no Windows 8 não.
Por que nem todos os contatos estão sendo baixados, parece que o Windows está baixando todos os contatos em "Meus contatos" no gmail. "Outros contatos" - contendo todos os contatos armazenados automaticamente, não é sincronizado.
Uma solução é entrar em "Outros contatos" no Gmail e importar contatos para "Meus contatos".