MySQL shows previously deleted data
"Transaction Isolation Modes" let you see data even after it has been deleted.  Some modes effectively "take a snapshot of all data", then let you see only that data until you COMMIT.

I doubt if that is what is causing what you see.  It would be very rare.  It would need longer timeouts than are reasonable.  Have you changed any from their defaults?

Note that I am also saying that you had to start a transaction and and not finish it for a long time; plus sometime in the middle a DELETE occurred from a another connection.

Look at the VARIABLES tx_isolation and autocommit and %timeout%.  Show them to us, plus sketch out the transactions you have.

Another answer:  You have a caching layer outside MySQL that is causing the problem.