Help with outlook search

I having been having trouble for months with search on outlook. Where do i go because the companies that i have paid to host the outlook 365 have not been able to solve it. The problem, Neither the web browser or the desktop app returns all the emails for a search. The desktop and web browser returns different emails from each other.  For example, if there were 10 emails that matched a search criteria, the desktop would return 1,5,6,7,9 and 10. The web browser would return 3, 5,6,7 and 9. That is just an example and not the true results. 

Thanks. 

Jeff Jacobson

email address removed for privacy reasons