Firebase won't accept SHA1 keys previously used with deleted app

I have weird issue with adding SHA1 keys to my Android app. Everytime I try to add them, I've got a message "This SHA1 is already used on another project", or something like this. The problem is that I do not have any other project where the SHA1 keys could be used. Previously I had the app in Firebase with same keys, but then I removed that app, and it seems like Firebase still remember that somehow, and keeps telling me that SHA1 keys are already used with another project. How could I resolve it?