You are using the term PBX, but at the same time said that you want only about 40 phones per location.
A PBX is normally larger that 40 phones, more expensive and with a lot of features that make maintenance hard and expensive.
On the other hand, the key systems evolved where they now have most of the features of the big PBX at a fraction of the cost.
A key system could have up to several hundred phone, voice mail, and interface with T1 trunks or a posible VOIP solution.
If you will like to have more details,contact me at firstname.lastname@example.org