This is indeed true. You need Windows server cals either for every device or every user that would connect. I would suggest trying out scalix activesync and blackberry activesync clients if you want to avoid paying this.
What about in a Windows shop? If you're licensing "per seat," and all the computers have a Windows CAL, do you really need Windows CALs for the BBs? That seems... well, really stupid. I can't imagine most companies actually complying with that. If you don't need CALs for the BB, than I don't think it would be any different in a linux shop... The Scalix server would need a CAL to communicate with the BES server.