Eu finalmente consertei isso fazendo "Limpar" em "Alterar o que a Cortana sabe sobre mim na nuvem" nas configurações de "Permissão e histórico". Depois disso, eu também re-instalei Cortana no telefone, não tendo certeza de que o passo era necessário também.