CRM Traking issues

We have a client who chose the track all emails option. Some of his machines are tracking very slowly or tracking quickly but not chnaging the icon in outlook to show they have been tracked. This is causing issues where the emails are in the wrong order in CRM or the client is unable to clear the inbox as he has lack of confidence that they have been tracked - any ideas??