Push messaging isn't really that hard. Sure, one connection per device adds up, and you've got to manage the queue of messages, and authenticating devices, etc.
The hidden challenge is tracking connection tracking timeouts in stateful firewalls and NAT gateways, so you can keep connections alive with the minimun of data exchanged. This is like if ISP A has a clean network, you only need to ping once an hour, but any packet sent will be recieved without delay; but ISP B needs a ping every 60 seconds or further packets will be dropped without notification. This isn't that hard either.
Bandwidth of push messaging is nothing compared to app downloads, and probably more of the effort would be on attracting quality applications and vetting applications and maintaining business relationships.
All that said, Google lets non-play apps use Google push, as long as the phone has play services, not sure why Apple would do it differently.