How to get a notification when user is blocked following flood I'm trying to get an email sent to me every time an account is banned following a flood (5 tries). 

Unfortunately, a user that is blocked isn't set to "status = 0", so I cannot use a rule based on user status. I did a few search and couldn't find Rules integration with the Flood Module. 

Is it part of the core? Is there anything other way to provide Rules integration with Flood?
Yes, Flood is part of core (it lives in includes/common.inc, and because Rules is a contrib module, there is no set way to integrate cleanly in Drupal 7. 

The one thing you might be able to do is to do a form_alter() on functions like user_login_final_validate($form, &amp;$form_state), since if a flood event has been triggered they will include a form value such as $form_state['flood_control_triggered'] which, when it is not empty, will indicate that a login attempt has been blocked. Then of course your custom form_alter implementation can call any Rules events it likes.

This is totally untested so I can't verify that it would work, but for now there doesn't seem to be an easy or clean way to do this in D7.