ActiveSync not working for few mailboxes

Are there FEW mailboxes administrative user accounts?

Did your users that have problems come from and oder SBS. Look at the groups they are members of. If they are admins or account admins it won't work.

Also check in that the accounts inherit their permissions properly:

http://alanhardisty.wordpress.com/2010/03/05/activesync-not-working-on-exchange-2010-when-inherit-permissions-not-set/
http://blog.nick.mackechnie.co.nz/post/2009/11/20/Exchange-2010-Active-Sync-Issue.aspx
http://aztech.net.au/node/137

Make sure Active Sync is enabled for said users.

@Carolchi: Issue is with Exchange 2003.

@Neilsr: Only couple of mailboxes are member of administrator

Forgot mention that Sync issue is with the Inbox. All other things like Contacts, Calendar are Syncing properly for the effected user.

What devices/device OS for working and not working?

All are Windows OS based devices.

What OS version? 4.0, 5.0, 6.0, 7.0?

It is 6.0

Normally it's an AntiVirus problem on the Exchange server.

I am sure you have seen this article before:
https://www.experts-exchange.com/Software/Server_Software/Email_Servers/Exchange/A_1798-Exchange-2003-Activesync-Connection-Problems-FAQ.html

@MegaNuk3: I follow this article first when ever i face issues related to Exchange 2003 ActiveSync.

Finally, We created a New Mailbox Store Database and Restore the database from the backup.

Install this:
http://support.microsoft.com/kb/957191

and if that doesn't work, delete the exchange account off the mobile device then download the mobileadmin tool and delete the device pairings for the affected users

Then try setup a device again. Does www.testexchangeconnectivity.com work for the affected users?

so is it working now or not?

Thanks for the update

We created a New Mailbox Store Database and Restore the database from the backup.