I manage a SBS 2003 box. Many users connect to it using mobile devices like iPhone, WM6 and Android. No one has any issues. I have one user who has a Droid by Verizon phone who just can't receive her own email via her phone (she can send mail but no receive).
* I tried my own mailbox on her Android phone and she can see everything in the inbox and send mail, as me.
* I tried her mailbox from my Android phone and I can see her mail and send mail as her.
* When I try her mailbox on her droid phone she cannot see her mail but she can send just fine.
I have to completely delete one Exchange account from an Android phone to recreate it (for the same or different user) so it's not like one accounts settings could be affecting another account.