Thanks for the fast response.
I'm positive that there are no more files on the file system. In fact I deleted the whole media library folder in the file system.
Ok upon checking again I can see that all files for that specific folder where it's not working are in DB as well as the blob storage. There are 74 files, but in Kentico backend I only see like ~35.
That's the really strange part. Everything seems correct but I still can't see or access it with permanent url.