Well, since no one else is experiencing this problem with RIM or Verizon, I don't think we can point to them.
I would ask you to do a couple of things to trouble shoot. One, ask your other BB user to PIN message your bosses BB. See how time that takes. Two, ask the other BB user to send a simple message to your bosses BB mail address (i.e.,
). Both of those messages should be delivered almost immediately, within a minute.
You might want also, meanwhile, to go to your bosses BIS account (assuming BIS... you didn't say) and delete his account, and then set it back up again. Likewise, delete the service books off his BB (Options, Advanced, Service Books, choose the ones with the @ email address, click to delete. You can resend the service books from the Verizon BIS website.
If you are BES..., could be something internally.