might have to do with older hh code. maybe the Hh need to be re-activated on the BES. of the users that are not working do you see the phone number within the bbmgr for them?
There's a BES setting which can be used to resend the policies to the handhelds every xxx hours, days, etc. I use it to send the policies once per week to make sure the HH's have the latest policy.