Actually I am new to the BB Administration Service and we are having this issue for a while now where the last contact date is not updated evenly for all users and some of them are saying that they receive emails on outlook faster than their handsets and sometimes the difference is really noticed and could reach 10-40 minutes.

We talked to our service provider and they told us to apply the KB20608 for configuring the throttling policy on exchange 2010 and to remove the additional users from your BES.

Which we did and still not affecting much and still suffering with some of the users.

Any Idea for solving that..

You don't list what version of Exchange 2010 or Blackberry you're running, but the issue about a delay you describe is known.
The latest maintenance release MR5 for SP2 or MR2 for 5 SP3 contains the improvements supposedly fixing it on the BES side.
For Exchange 2010 you need to apply the Sp1 RollUp 3 and do remember to get version 3of the rollup. If you're not on SP1 on 2010 yet then begin with updating BES.
Alternatively as I had to do on my servers, if you only have like a handfull of users constantly having that problem, assign a static agent to them. You do this via logging into the Blackberry administation service--Click Manage Users--Locate your user--Click the Component Information tab--Click Edit user and then set Turn on static agent to Yes and select a number between 200 and 399. You can have multiple users on the same static agent. I usually leave around 5 per agent and about 2-3 agents.