Office 365 contacts not fully syncing

I am dealing with an odd issue. Have a user who has about 14,000 contacts. Outlook and OWA both show the correct amount of contacts. The user has a samsung galaxy phone and it will sync most of the contacts and then stop. Going in to account and telling it to sync does nothing more. I have replicated the issue on multiple samsung phones. When I add the same account to an iPhone it syncs all the contacts no problem. I turned on activesync logging for user and I have a copy of the logs but to be honest I am not sure what to even look for in the logs. There is nothing that stands out to me. I found one microsoft document that mentions this issue and the solution was to set ActiveSync mailbox policy to Unlimited. I checked and this setting is already in place (looks to be the default policy). :
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Vasil Michev (MVP)Commented:
I take it you are using the default mail application on the device? If so this looks like a limitation of the app, try another one.
MLV CMCommented:
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.