Small & simple yet effective change.
Like in your friends list how you can see if someone is online by whether or not their name is a certain color, grey is offline and orange is online (colors vary from theme to theme).
Would it be possible for the Address book to do the same? There's people who I pm on a regular basis that I'm not necessarily friends with. Would make it easier and faster to know who's online and who's not.