After migrating from Office 2007 to Office 365 I've been facing a variety of weird issues.
One of them is that contacts don't autofill for certain users.
To explain that further, before migration I took a PST copy from all machines and when I finished with migration to Office 365 and downloaded Outlook, I've imported it as normal. Now, most of the people that work here haven't been religious with saving contacts of clients but Outlook was smart enough to remember all past email addresses and therefore filling them in when you type the initials.
Since the migration, that's still the case for some people here but for some others this doesn't work. So when they compose a new email and want to reach out to a client, his email won't appear if you type in the initials (although I've imported the PST and all the email history is there) and so they have to look for past conversations, copy their email address to send them a new one.
This is time consuming and also very unproductive, but I'm not entirely sure how to solve it or why it happened only to some people. If it was everyone I'd know that something is wrong or that contact history is erased. Because it works for most of our staff though, I can't think why it happened.
I've also checked the option in mail settings (file/options/mail/send mails) to auto-complete addresses in CCd and other emails but still nothing.