you can create a Sticky_Service this will re-start your service even if the OS decides to kill it, it will automatically get re-started, you can schedule the service to re-start every so often, let's say every 30 seconds or so and you can ping your server and check if there's a connection.
Push notifications are your best option (assuming that the device and server are connected to the internet). You don't need to show a notification when a message arrives.