MySQL shows previously deleted data We're running MySQL on Azure. We have three very small databases.

The main database is POI and it hold 11 static records. During the day a few records may be added and deleted again within 1-2 hours.

We typically have 5-10 mobile users who poll the POI-DB for all 11-15 records every 60 seconds.

Several times every day, we do get some corrupt data from our SQL query. We often see two records which were deleted from the database two months ago.
What can make such a simple database become unreliable?

Server: eu-cdbr-azure-north-d.cloudapp.net via TCP/IP
Server type: MySQL
Server version: 5.5.45-log - MySQL Community Server (GPL)
Protocol version: 10
PHP extension: mysqli 
PHP version: 5.4.42


--edit 

I've changed our database to InnoDB. I still get the ghost-data.
The ghost data is not visible, when I use phpMyAdmin to view the POI-DB.

I started to measure the database connection time and realized that they sometimes are 1 - 5 seconds, so I's very likely to have concurrent requests, when the connection request is stocked. 

Do I need to do some special tricks to handle concurrency?
The long connection times are probably caused by reverse DNS lookup. We will disable that now.
"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.