To add my (probably not most typical) opinion on this:
I am very conservative about purchasing of apps. E.g., I am not spending many dollars on games.
But in this situation, I think Push for Exchange would be very appropriately a feature of the paid version of the app.
Here is my thinking behind it:
Exchange is typically a part of a business environment. If one wants PUSH (very few people actually need it), - that person can afford $5.
Of course, this applies to the countries with a more or less developed economy (US, Europe), where people pay almost as much for a cup of crappuccino.
Maybe I am wrong, but I doubt that people who cannot afford it (in countries with very poor economies) would need PUSH in Exchange.
But on another hand, - the sense of entitlement is omnipresent these days. So, I wouldn't be surprised about 1-star complaints. I still think your decision is correct.