According to the Firebase Google Group, this is a known bug with Firebase:

This is a known bug on our end. As you noted, after deleting a user, existing auth tokens are still valid and can be used to read and write to your Firebase database. Security Rules are still enforced on these tokens and that user will still only be able to access their own Firebase data (if your rules are set up as such). Those auth tokens will be valid until they expire. There is currently no workaround for this bug although we are going to be fixing this in a future release.

https://groups.google.com/d/msg/firebase-talk/Yr_wn02q0bk/eTM9hop3paoJ

The only thing I can think to do is check whether you can read to your users area, and if there's nothing there, force a log out.