I haven't really done much addon development but can't you just setup a timer of some sort to check their level and store their old levels as variables on the client side?
If not then I suppose you could try to find some event that happens fairly regularly but not too often and check then in addition to when you log on and when you see them log on. Maybe when you mount up or something.
No clue... just throwing out ideas. It can't be that hard to scan through the list of friends you have online and query their level and it can't be that hard to find some way to trigger this in such a way that it doesn't use a ton of CPU or happen only rarely.