Okay, I found the problem (after adding myself to every group one of the users was in and still failing to duplicate the problem after an ExchangeIS restart) and I feel pretty stupid. It turns out that the problem accounts weren't inheriting permissions in AD... in fact my account wasn't inheriting either, but it was working because I had a group in Send-on-behalf-of which included the BES admin, so while I had permission problems it didn't look like I did because Send-on-behalf-of was covering up the problem.
D'oh!
While I found it odd that the bes admin was not listed in my permissions list, he was on the container and my BB worked, so obviously it was right... and now I feel retarded ;)
I'm going to each problem account and re-enabling inheritance (which was disabled I suspect due to a permissions balls up we had last year) and now life is good
@hindgrinder
That isn't so you can see what you should be in, it's simply to check that one group doesn't belong to another which belongs to a protected group. It's basically so you can get a true view of the groups someone belongs to, all the way back along the MemberOf chain.