Yes, codec licensing costs are one of the reasons people choose to not use the better codecs. Also, yes there is a CPU trade off as well.

The decision is more complicate with many trade offs. But in general, the OPs issues are either fundamental network ones or an intentional choice of one of his providers (typically for cost reasons - manifested in some manner).