There is a difference between BES accessible and including BES service. All BBs are BES accessible, however the BES software is not free, actually it's very expensive and you need either Microsoft Exchange, Lotus Domino or Novell GroupWise Server.
Most corporations use BES software on top of their standard email servers, while some third party companies will provide BES service for an additional monthly fee, on top of whatever you are paying to your cellular carrier.
I don't know about Alltel, but I don't think Verizon will allow you to use the BBs without a BB data plan. But then again, it never hurts to ask. The worst they can do to you is tell you no.