Gateway devices maintain presence information for various mobile devices. Each gateway is associated with a zone and manages presence information only for mobile devices associated with that zone. Courier devices back-propagate presence information for the mobile devices to respective gateways based at least on the respective zone associated with each mobile device. The gateways and couriers are dynamically configured such that messages can be pushed from a provider application to a mobile device via any gateway and any courier.