That's a great idea! i have it in my mind for long time, thinking about post a brainstorm!
I dont think you will be flooded with notifications, think about Windows Messenger, XYZ contact gets online/offline and thats it all.