A Push-to-X over Cellular (PoC) server (351) receives a server registration message (301) for a first called device from a second server. The PoC server (351) receives a PoC invitation message (310) with PoC preferences and a message (313) from an originating device (311). The PoC preferences determine what device to call first (e.g., a mobile device 315, 317) and how many hops the call can be forwarded (e.g., to a voicemail server) if the first-attempted device is not available, before discontinuing the connection. If a trigger, such as time elapsed, occurs for the first-attempted device (350) and the PoC preferences permit, the PoC server (351) sends an invitation message (360) to the second server (391). If the second server (391) is a recording server, the invitation message (360) includes a message (363) from the originating device that is compatible with the capabilities of the recording server (391).