In the PowerApps [All Apps] list, the deleted apps are appeared.
In principle, it is unnecessary to display deleted apps, so I think that they should be updated immediately, but because they are heavily cached by design, they will not be removed from the list for a long time.
As this situation has an obstacle to the use of the app, please consider early improvement.
Thank you.