Oh! Oh! Oh!
I thought of a perfect way to impliment it client side.
Do it backwards. Instead of the client keeping a list of people to watch, have the client keep a buddy list of users to notify about you status.
Every time you change your away status, also send a NOTICE all the people on you buddy list.
When you disconnect from the server, first send a notice to everyone informing them you are offline.
When you connect to the server, send a notice to everyone on your buddy list to inform them that you are online. Your buddys then respond with a notice to you informing you of their status. (People who don't respond, are most likely not online.)
Client parses all this notice traffic and maintains a list of everyone's offline/online status and away info.
The notice traffic would work very efficiently and would not cause anyone without the plugin any grief.
Also, make the notice messages human friendly so they'll also be usefull to people without the plugin: "NOTICE billy,joe,rae,bob :I am online" No need to hide any messages from the user.
That would actually be enough to make it usable, but there's more.

You can also use ISON when you connect to check who's online (in case you have people in your list that don't have the plugin or have some other problem that prevents them from responding).
Use ISON periodically to check for dropped connections.
Watch for 301 away messages and 401 no such nick messages as they are recieved to use as a backup method to keep updated on everyone's status.
And you can always use a whois on anyone you find online that doesn't respond to your notices to retrieve their away info.
Should be enough info there to start coding.