They could simply check whether the hash they stored corresponds to your email address.
Good catch, I missed in the conclusion that they suggested hashing the email if necessary (earlier in the article they mentioned only hashing the identifier).
In this case they will have to provide their facebook id which they probably did not store and have a means of authentication which they deleted.
There is either Personally Identifiable Information, or there is not.
If there is then identity can be confirmed and the account deleted.
If there is not then there is nothing that needs to be deleted.
You're right that could be an issue, but hopefully anyone who registered via Facebook will take care to add an email/password to their account and disconnect Facebook before they delete their Facebook account.
I’m not sure I would trust all users to keep that in mind.
I'm sure I would trust users to not keep that in mind. Most user's aren't very good an this stuff.