Would you be able to use real-time updates for this to avoid polling? http://developers.facebook.com/docs/reference/api/user/ I'm not sure if it notifies you on friends changes or just the user that authed your app. I assume the latter.
However, there's probably some worthwhile activity in monitoring wall posts from ex's in the period running up to the status change?
Humans are completely unpredictable mind... haha :)