To get new messages, you could simply use long polling so it becomes push instead of pull. For checking if the user is online (I'm assuming your clients are running in web browsers), you can use the onbeforeunload to send a HTTP request that the user is leaving. Of course, you still have to poll at regular intervals because the user might have put his computer to sleep which wouldn't trigger onbeforeunload but your interval can now even be as high as 60 seconds because most clients will trigger onbeforeunload.
