Keep a file for each logged in user that is updated each time a new message arrives (maybe with the line numbers of the messages?). Then all the client has to do is check if the updated time has changed since the last access, and if it has, only THEN access the database. The file can be deleted if a user logs out, and also deleted if an expiration time is reached (let's say if the user hasn't logged in for 24 hours), thus keeping the number of files relatively small, or at least smaller than your total number of users.

Having the client listen for messages instead of checking for them would of course be the more elegant solution, but that method requires a good deal more complicated programming and most likely comes with problems of its own.

A third possibility is to vary the access speed so you get 1 second accesses within x minutes of your last message (in or out), then a gradually slower access speed down to eventually 30-60 second accesses. This should significantly cut database calls without hurting your messaging system much or requiring complicated rewrites.