We're seeing a lot of reported cases where customers conversation history is not being saved.

The most common reason is that your mailbox may have over 1000+ folders, if you might be in this situation and your users are reporting this, then you can check their mailbox by performing this quick powershell cmd to count the folders in their box.

Get-MailboxFolderStatistics “user” | ? {$_.FolderPath -eq "/Inbox"}
(Get-MailboxFolderStatistics “user”).Count

If it's over 1000+ then reduce it to below this number (general house-keeping wouldn't go a miss :)